KAKA学python 发表于 2021-2-16 17:12:31

时间复杂度

萌新，想问问这题时间复杂度为啥是这个

昨非 发表于 2021-2-16 17:19:38

选择题还是用排除法吧{:10_279:}

Daniel_Zhang 发表于 2021-2-16 18:45:06

本帖最后由 Daniel_Zhang 于 2021-2-16 18:48 编辑

while 的时间复杂度是 logn

for的时间复杂度是 n

因为 for 循环了 (n + 1) - 1 = n 次， while 在 for 里面，所以时间复杂度为 O(nlogn)    欧米伽打不出来，抱歉{:10_245:}

A 是单层 for 循环
B 是双层 for 循环嵌套
C 是单独的一个 print 或者赋值等其他的什么东西，时间复杂度为一个常量
D 是 for while 嵌套循环

KAKA学python 发表于 2021-2-17 13:54:30

Daniel_Zhang 发表于 2021-2-16 18:45
while 的时间复杂度是 logn

for的时间复杂度是 n


想问下while的时间复杂度为什么是logn？

Daniel_Zhang 发表于 2021-2-17 14:04:03

KAKA学python 发表于 2021-2-17 13:54
想问下while的时间复杂度为什么是logn？

这个就是约定俗成的，你要真的去推导可能还挺麻烦的

这些东西其实也就是靠记的，没什么特别的东西

你可以尝试一下百度看看为什么 while 的时间复杂度是 logn

巴巴鲁 发表于 2021-3-8 21:36:28

while(n--)
{
}
时间复杂度就是O(n)啊，和是不是while没有关系，要知道while和for是相似的
这个我理解的是1+2+3+...+x <= n
即(x^2+x)/2 <= n
即x^2 <= n
所以x = logn(以2为底)，那时间复杂度就是logn了
页: [1]
查看完整版本: 时间复杂度