Basi c вопрос сложности времени. Временная сложность этой простой функции

Question

Я очень плохо знаком со сложностью времени. Я ищу временную сложность этого кода

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

Я знаю, что l oop сделает его O (n), но тогда счет также равен O (n) в python, это сделало бы эту функцию O (n) или O (n ² )?

Answer 1

У вас есть все oop в пределах всех oop:

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)

Answer 2

O (N ^ 2). Внешний l oop выполняет n раз внутренний оператор (который равен O (n)), поэтому мы получаем квадратичную c сложность.