时间戳

首页 > 解决方案 > 使用 Big (O) 进行时间复杂度分析

python - 使用 Big (O) 进行时间复杂度分析

问题描述

arr = [1, 2, 5, 6, 7]
total = 0
for i in range(len(arr)):
    total += sum(arr[i:])

上面代码的时间复杂度是O(n^2)还是O(n^3)，因为列表arr的切片造成的混乱。那么切片 arr 是如何影响时间复杂度的呢？

标签： pythonlisttime-complexitybig-oslice

解决方案

对列表进行切片是切片O(k)的k大小，在这种情况下四舍五入为O(n). 但是，在这种情况下，时间复杂度仍然是O(n^2)，因为arr[i:]与 是相加的sum()，而不是相乘的。如果我们将其分解为两个单独的步骤，我们可以看到这一点：

for i in range(len(arr)):        # executes n times
    things_to_sum_over = arr[i:]      # runs in (k -> n) time
    total += sum(things_to_sum_over)  # operates over (k -> n) elements

这给出了一个总数 n * 2(k -> n)，或2n^2= O(n^2)。

推荐阅读