UC知道python 时间复杂度
来源：百度知道 编辑：UC知道 时间：2024/05/17 04:00:50
问输出和时间复杂度。谢谢。
(a)
x = 0
a = 6
b = 6
c = 1
for i in range(2*n):
x = x + c
c = c + b
b = b + a
print x
(b)
x = 0
for i in range(1,n):
for j in range(1,n):
x = x + j/float(i*(i+1))
print x
(c)
x = 1
while x < n:
x = x * 2
print x
谢谢两位，请问输出结果呢？另外，第三个为什么是O(logn)? 万分感谢。
(a)
x = 0
a = 6
b = 6
c = 1
for i in range(2*n):
x = x + c
c = c + b
b = b + a
print x
(b)
x = 0
for i in range(1,n):
for j in range(1,n):
x = x + j/float(i*(i+1))
print x
(c)
x = 1
while x < n:
x = x * 2
print x
谢谢两位，请问输出结果呢？另外，第三个为什么是O(logn)? 万分感谢。
Hey dude! 判断时间复杂度跟核心语句的执行频次有密切关系，执行频次越多时间复杂度越高。第三个循环的核心语句是:
x = x*2
假设我们设它的执行频次为f(n)，根据题意我们能够得到这种规律，执行1次x=2,2次x=4，所以该核心语句的执行次数f(n)应该满足: 2^{f(n)} < n， 得出f(n)< log_{2}(n)，更多关于时间复杂度的知识可参考这篇博文：
http://blog.csdn.net/zolalad/article/details/11848739?readlog
第一个是 O(n) 第二个是O(n^2) 第三个是 O(logn)
(a) O(n)
(b)0(n^2)
(c)O(logn)