分析循环与嵌套循环
计算单层循环、嵌套循环以及范围不断缩小的循环的时间复杂度，例如二分查找或三角形迭代。
分析循环与嵌套循环 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
单层循环：O(n)
最简单的循环会运行其主体 n 次，因此是 O(n)。增大步长会改变次数，但不会改变复杂度类别。首先要数清楚循环主体运行了多少次。请查看代码。
# O(n): body runs n times
def count_ops_linear(n):
ops = 0
for i in range(n):
ops += 1 # constant work
return ops
print(count_ops_linear(100)) # 100
# Still O(n): step=2 halves count but same class
def count_ops_half(n):
ops = 0
for i in range(0, n, 2):
ops += 1
return ops
print(count_ops_half(100)) # 50 => O(n)嵌套循环：O(n²) 及更高
两个嵌套循环各运行 n 次，会得到 n × n = O(n^2)；三个循环会得到 O(n^3)。但如果内层循环只运行固定次数，整体复杂度仍然是线性的。
def count_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(n): # n iterations each
ops += 1
return ops
print(count_pairs(10)) # 100 = 10^2
print(count_pairs(100)) # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)三角形循环：O(n²/2) = O(n²)
当内层循环从 i+1 开始时，迭代次数会形成一个三角形：n(n-1)/2。舍弃一半后，它仍然是 O(n^2)。要求所有元素两两配对的问题通常都属于这种情况。
def count_unique_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(i+1, n): # n-1, n-2, ..., 0
ops += 1
return ops
print(count_unique_pairs(10)) # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 dropped缩小范围的循环：O(log n)
当循环变量每一步都减半时，复杂度就是 O(log n)。关键问题是：范围按倍数缩小（log n），还是按固定增量缩小（n）？请查看代码。
def count_log_ops(n):
ops = 0
i = n
while i >= 1:
ops += 1
i //= 2 # halve each iteration
return ops
import math
for n in [8, 16, 64, 1024]:
ops = count_log_ops(n)
print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closely内层范围不断缩小的嵌套循环：O(n log n)
一个运行 n 次的外层循环，加上一个 O(log n) 的内层循环，会得到 O(n log n)——这正是归并排序的结构。识别出 O(log n) 的内层步骤，是分析排序算法的关键。
import math
def count_n_log_n(n):
ops = 0
for i in range(n): # n iterations
j = n
while j >= 1: # log n iterations
ops += 1
j //= 2
return ops
for n in [8, 32, 128]:
ops = count_n_log_n(n)
predicted = int(n * math.log2(n))
print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')相互依赖的内层循环
当内层循环的范围取决于外层索引时，要数总迭代次数，而不是每一步的次数。一个运行 0..i 的内层循环，其总和为 n(n-1)/2 = O(n^2)。请查看代码。
# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
ops = 0
for i in range(n):
for j in range(i): # runs 0,1,2,...,n-1 times
ops += 1
return ops
print(sum_inner_i(10)) # 45 = 10*9/2 => O(n^2)
# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
ops = 0
i = 1
while i <= n:
for j in range(n // i):
ops += 1
i *= 2
return ops
print(sum_inner_n_over_i(64)) # ~ 64*6 = 384逐步分析冒泡排序
冒泡排序会比较 n(n-1)/2 次，因此复杂度是 O(n^2)。即使设置了提前退出，逆序输入仍然需要完成每一次比较。对于大型输入来说太慢了。
def bubble_sort(arr):
n = len(arr)
comparisons = 0
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # early exit if sorted
break
return comparisons
arr = list(range(10, 0, -1)) # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}') # 45 = 10*9/2遍历字符串和子字符串
请注意：Python 的切片复杂度是 O(k)，并不是没有成本；在循环中使用 + 拼接字符串的复杂度是 O(n^2)，因为每次都会复制内容。请改用 ''.join(parts)。请查看代码。
# O(n^2): string concat in loop
def build_bad(n):
s = ''
for i in range(n):
s += str(i) # copies s each time!
return s
# O(n): join is a single pass
def build_good(n):
parts = []
for i in range(n):
parts.append(str(i))
return ''.join(parts)
print(build_good(10)) # '0123456789'多个输入参数
有两个输入时，复杂度可能需要同时使用两者：分别处理时是 O(m + n)，嵌套处理时是 O(m × n)。图算法通常表示为 O(V + E)。请为每个变量使用清晰的名称。
# O(m + n): two independent loops
def independent(m, n):
a = sum(range(m)) # O(m)
b = sum(range(n)) # O(n)
return a + b # total O(m + n)
# O(m * n): nested
def nested(m, n):
count = 0
for i in range(m): # O(m)
for j in range(n): # O(n) each
count += 1
return count # O(m * n)
print(independent(5, 10)) # 10 + 45 = 55
print(nested(5, 10)) # 50循环嵌套与顺序调用
函数调用并非没有成本——其中的内层循环也要计算在内。调用 O(n) 的辅助函数 n 次，就会得到 O(n^2)。分析时一定要查看黑盒调用的内部实现。
# Naive string matching: O(n*m)
def naive_search(text, pattern):
n, m = len(text), len(pattern)
matches = []
for i in range(n - m + 1): # O(n)
if text[i:i+m] == pattern: # O(m) comparison + O(m) slice
matches.append(i)
return matches
# Total: O(n*m)
print(naive_search('abcabcabc', 'abc')) # [0, 3, 6]实践：一眼识别复杂度
养成这样的习惯：数清循环嵌套层数，检查内层循环是否依赖外层循环，并留意函数调用和切片中隐藏的成本。这段代码是一道可以动手尝试的谜题。
# What is the complexity of this function?
def mystery(nums):
result = []
for i in range(len(nums)): # O(n)
for j in range(i, len(nums)): # O(n) worst
if sum(nums[i:j+1]) == 0: # O(n) slice + sum!
result.append((i, j))
return result
# Answer: O(n^3) -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)快速检查
快速检查一下——看看循环分析技巧掌握得有多好。请相信自己的推理。💪
课程回顾
回顾：嵌套循环相乘，独立循环相加；每次减半的内层循环会得到 O(n log n)；调用和切片中的隐藏成本也必须计算在内。
常见问题解答
「分析循环与嵌套循环」课时是免费的吗？
是的 — 「分析循环与嵌套循环」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「分析循环与嵌套循环」这节课中我会学到什么？
计算单层循环、嵌套循环以及范围不断缩小的循环的时间复杂度，例如二分查找或三角形迭代。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「分析循环与嵌套循环」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 从零理解大 O 记法
- 分析循环与嵌套循环
- 递归与递归树法
- 空间复杂度与权衡