时间复杂度

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

萌新，想问问这题时间复杂度为啥是这个 FireShot Capture 27 - - https___moodle.gtiit.edu.cn_moodle_pluginfile.php_39389.png

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

选择题还是用排除法吧

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) 欧米伽打不出来，抱歉

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了

账号		自动登录	找回密码
密码			立即注册