Блог

Главная - Вопросы по программированию - Какова временная сложность этого кода на python? Является ли это O(sqrt(n)) или O(n), потому что sum() имеет O(n)?

Какова временная сложность этого кода на python? Является ли это O(sqrt(n)) или O(n), потому что sum() имеет O(n)?

#python #time-complexity #analysis #space-complexity

#питон #временная сложность #анализ #пространство-сложность

Вопрос:

Вот код— Он возвращает число простых чисел, меньшее n.

 def countPrimes2(n):  if n lt; 3:  return 0  primes = [True]*(n//2)  for i in range(3, int((n**0.5)) 1, 2):  if primes[i//2]:  primes[i*i//2::i] = [False]*((n - i*i - 1) // (2*i)   1)   return sum(primes)

Комментарии:

1. Вы не учитываете время, затраченное на задание среза.

2. Первая строка фактического кода такова [True] * (n // 2) . Это уже O(n).

3. @FrankYellin Не должно ли это быть O(log n), потому что пространство выборки уменьшено вдвое?

4. @batman: Если ты удваиваешь n , ты все равно удваиваешь n//2 .

5. @бэтмен. Ваш вопрос ко мне указывает на то, что вы не совсем понимаете, что означает обозначение O (). Ты действительно. нужно понять, что означает O(n) и O(sqrt(n)), прежде чем спрашивать, что такое O() конкретного алгоритма.

Метки: ,