关于算法的时间复杂度 关于算法的时间复杂度,下列说法正确的是

许多学习编程的人，包括我这名小学生[憨笑]，至少都会有一些算法基础[狗头]，而一提到时间复杂度，大家肯定都不陌生吧！

我们今天就来聊一聊时间复杂度。

当我们要比较哪一个算法的运行时间、效率更高时，可能要测每个算法的运行时间，但问题是，每台电脑的运行速度可不一样，如winx64和winx32,一个每次计算64位数，一个每次才32位，所以运行时间会出现很大差别。

这时，我们就要用时间复杂度来表示了！

我们先来看看这几组代码:

print("hello world")

for i in range(n):
    print("hello world")

for i in range(n):
    for j in range(n):
        print("hello world")

请问哪组代码的运行时间长？如果n>1,肯定是第三组运行时间长。

那还有没有办法可以表示哪组运行时间长？

这就是我们今天要讲的用来表示算法效率的方式——时间复杂度

为了更好的理解它，我们先来估计做一些事件的时间:

眨一下眼睛 几毫秒

口算"39+68" 几秒

烧一壶水 几分钟

睡一觉 几小时

完成一个项目 几天/几个星期/几个月

飞船从地球飞出太阳系 几年

而毫秒、秒、小时、年我们称之为单位，时间复杂度也有单位

O(1)就是一个时间复杂度，“1”则代表单位

如

print("hello world")

我们定义这段代码的时间复杂度为O(1)

for i in range(n):
    print("hello world")

因为这段代码比print("hello world")多运行了n次，所以我们定义它的时间复杂度为O(n)

for i in range(n):
    for i in range(n):
        print("hello world")

以此类推，这段代码比

for i in range(n):
    print("hello world")

多运行了n次，所以时间复杂度为O(n2)

那么问题来了，这几组代码的时间复杂度为几呢？

print("hello world")
print("hello world")
print("hello world")

for i in range(n):
    print("hello world")
    for i in range(n):
        print("hello world")

大家的答案可能是O(3)和O(n+n2)对不对？错了。

因为O()中的"括号里代表的是一个单位，如果写成O(3),就相当于问你一壶水烧几分钟，没有人会回答烧了几个3分钟。

所以像第一组代码一样，我们定义的单位是1，所以将O(3)写成O(1),n2+n不是一个单位，所以O(n2+n)写成O(n2),+n就被忽略了。

我们再来看看这组代码:

while n>1:
    print(n)
    n=n//2

这次时间复杂度又有所不同呢？

我们可以发现，代入n=64,输出为:

64,32,16,8,4,2

运行次数为6次，发现2^6=64

log2 64=6

时间复杂度就记为O(logn) ,省去了2

这种情况就是循环每次减半。

时间复杂度-小结:

1、一般来说，时间复杂度高的算法比时间复杂度低的算法慢

2、常见的时间复杂度(按速度排序):

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

3、复杂算法的时间复杂度:

O(n!)、O(2^n)、O(n^n)

今天就给大家讲到这里！