时间戳

首页 > 解决方案 > 基本时间复杂度问题。这个简单函数的时间复杂度

python - 基本时间复杂度问题。这个简单函数的时间复杂度

问题描述

我对时间复杂度非常陌生。我正在寻找这段代码的时间复杂度

def func(arg):
  list= []
  for i in range(len(arg):       
      list.append(arg.count(i)     
  return list

我知道循环会使其成为 O(n)，但是在 python 中 count 也是 O(n)，这会使这个函数成为 O(n) 还是 O(n 2 )？

标签： pythontime-complexity

解决方案

您在循环中有一个循环：

for i in range(len(arg)): # outer loop => O(n)
      arg.count(i)  # inner loop hidden inside a function => O(n)

就是这样O(n^2)。

如果你想要两个总和为 的循环O(n)，你需要这样的东西：

for x in range(N): # O(N)
    ... # do stuff

for y in range(N): # O(N)
    ... # do other stuff

整体复杂度将是循环复杂度的总和，所以

O(N) + O(N) = O(2 * N) ~= O(N)

推荐阅读