c*****m
发帖数: 1160 | 1 比如说，一段程序，没有调用子函数，有一个循环 for i=1 to 1000，那么复杂度应该
是 O(1)啰；
如果循环是 for i=1 to n, 那么复杂度应该是 O(n)？
现在问题是：在这个循环里（没有子函数）用了一个dict , python里的词典：
for i=1 to n
value=d[key]
这个dict的查询, 不是数组的直接access，应该最快也是sort算法的 O(nlgn)吧？ 那
么这段程序是否成了 O(n*nlgn)? | s*i
发帖数: 5025 | 2 Dict 的查询是 O（1），python这个应该能保证 | p**r
发帖数: 5853 | 3 dict就是hash
查key就是O(1)
【在 c*****m 的大作中提到】
: 比如说，一段程序，没有调用子函数，有一个循环 for i=1 to 1000，那么复杂度应该
: 是 O(1)啰；
: 如果循环是 for i=1 to n, 那么复杂度应该是 O(n)？
: 现在问题是：在这个循环里（没有子函数）用了一个dict , python里的词典：
: for i=1 to n
: value=d[key]
: 这个dict的查询, 不是数组的直接access，应该最快也是sort算法的 O(nlgn)吧？ 那
: 么这段程序是否成了 O(n*nlgn)?
|
|
