我不明白为什么时间复杂性中没有√n因子。这是代码
def sieve_of_erastothenes(max):
flags = [True] * (max+1)
num = 2
while num*num <= max:
if flags[num] is True: # if it is a prime number
cross_off(flags, num)
num += 1
return [i for i in range(2,len(flags)) if flags[i] is True]
def cross_off(flags, prime):
# no point in crossing anything before prime*prime
for num in range(prime*prime, len(flags), prime):
flags[num] = False
num += prime
外回路(num*num <= max(运行√n次。若已设置标志，则内部循环将运行n/p次。n/p的和，其中p只是素数，给出n*loglogn所以时间复杂度应该是O(√n*n*loglogn(。但无论我读到哪里，它都是O(nloglogn(
我想我已经在Matt Timmermans和rici的评论的帮助下找到了答案。我有两个误解
-
给定素数的内部循环运行
n / prime次。求和n/2+n/3+n/5+n/7+n/11。。。。已经考虑了外部√n因素。求和本身是，因为外部循环的。 -
如果条件的故障情况被计数为，但它被其他因素所压倒。所以我们可以把它写成
num => 2 3 4 5 6 7 8 9 10 11
sum => n/2 + n/3 + 1 + n/5 + 1 + n/7 + 1 + 1 + 1 + n/11...
sum => (n/2 + n/3 + n/5 ...) + (1 + 1 + 1 + 1....)
sum => (nloglogn) + (n) # Worst case. 1+1+1.. will always be less than n
O(nloglogn+n(=O(nloglogn(