python - 了解如何衡量函数的时间复杂度

Question

这是函数:

c = []
def badsort(l):
  v = 0
  m = len(l)
  while v<m:
    c.append(min(l))
    l.remove(min(l))
    v+=1
  return c

虽然我意识到这是一种非常低效的排序方式，但我想知道这样一个函数的时间复杂度是多少，因为虽然它没有嵌套循环，但它会重复多次循环。

Answer 1

术语

假设 n = len(l)。

迭代次数

外层循环运行 n 次。内层循环中的 min() 在 l 上运行两次(这里有优化空间)但是递增地减少数字(对于循环的每次迭代，l 的长度减少，因为你从每次都列出)。

这样复杂度是 2 * (n + (n-1) + (n-2) + ... + (n-n))。这等于 2 * (n^2 - (1 + 2 + 3 + ... + n))。括号中的第二项是 triangular number并发散到 n*(n+1)/2。

因此您的复杂度等于 2*(n^2 - n*(n+1)/2))。这可以扩展为 2*(n^2 - n^2/2 - n/2)，并简化为 n^2 - n。

BigO 符号

BigO notation 感兴趣的是整体增长趋势，而不是函数的精确增长速度。

删除常量

在 BigO 表示法中，常量被删除。由于没有常量，所以我们仍然使用 n^2 - n。

只保留显性词

此外，在 BigO 表示法中，仅考虑主导项。 n^2 优于 n，因此 n 被丢弃。

结果

这意味着 BigO 的答案是 O(n) = n^2，即二次复杂度。