Post

⚠️ 不是所有"嵌套 for 循环"复杂度都等于 O(n²)

直觉: 两个for循环嵌套复杂度就是 O(n²)

1
2
3
for x in setA:
   for Y in setB:

纠错:去真正推导这次具体的循环到底在做什么

比如这个场景,我使用而为链表,来记录跨目录选中的文件, 第一维度链表是文件的目录, 第二维度的链表记录的是文件名

此时如果查找一个文件是否是选中, 此时需要遍历这个二维链表, 那么如果分析这个遍历算法的复杂度是多少。

具体分析一下一次查找操作,要走的节点数,最坏情况是,外层节点+内层节点.

虽然这里也涉及到两个for循环嵌套,但是 外层是”一旦匹配就停下来,不会对每个目录都完整跑一遍内层”

代码层面的表示

1
2
3
4
5
for dir in set(dirs):
	if match(dir,target_dir):
		for file in file_set(dir):
			if match_file(file,target_file):
				do_something()

这里形式上虽然也是两个for循环嵌套,但是其实是由匹配条件的.

所以不是无条件的对每一个外层都执行一遍内层, 那样则是O(n²),比如冒泡排序

This post is licensed under CC BY 4.0 by the author.