算法笔记(八):复杂度分析(二)

2018-11-20 03:25:13来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

#感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

(一) 对数阶时间复杂度

1 def tset(n):
2     i = 1
3     while i <= n:
4         i = i*2

    上面这段代码,i 从1开始,循环一次乘于2,当大于n时,循环结束,我们可以得到2x = n。要计算上面这段代码的时间复杂度,求解x的值就行了,根据数学基础中和对数相关的计算,可以得到x = log2n = logn,所以这段代码的时间复杂度就是O(logn)。

        将代码修改成下面这样,很容易计算出,代码的时间复杂度是O(log3n)。

1 def tset(n):
2     i = 1
3     while i <= n:
4         i = i*3

        在对数中log3n = log32*log2n,所以O(log3n) = O(log32*log2n) = O(C*log2n),其中C是常量,根据渐进符号的定义,计算时间复杂度时,我们可以忽略常量,所以上面这段代码的时间复杂度也是O(logn),同理,所有对数阶时间复杂度的表示中,可以统一表示为O(logn)。

   如果一段代码的时间复杂度是O(logn),如果循环运行n次,那么时间复杂度就是O(nlogn)。

(二) 空间复杂度

  下面这段代码,和分析时间复杂度一样,因为只有第三行代码创建了一个大小为n的数组,其他不是常量就是不占用内存空间,所以这段代码的空间复杂度是O(n)

1 def test1(n):
2     a = 0
3     arr = numpy.arange(n)
4     for i in range(n):
5         arr[i] = i*i
6     return arr

(三)  最好、最坏、平均时间复杂度

 这里我们用之前线性查找的例子:

1 import numpy as np
2 
3 #找到结果,返回索引,否则返回None
4 def search(array,key):
5     for j in range(len(array)):
6         if array[j] == key:
7             return j
8     return None

最好时间复杂度: 如果第一个元素就是我们要查找的元素,那么代码的时间复杂度就是O(1)

最坏时间复杂度:如果最后一个元素才是我们要查找的元素,或者数组中根本就没有我们要查找的元素,那么代码的时间复杂度就是O(n)

平均时间复杂度:查找元素在是否在数组中有2种情况,在数组中(0...n-1)和不在数组中,那么总共就有 n+1种情况,我们将需要查找的元素(可能运行的次数,第n个元素和不在数组中运行次数都是n次)相加除以n+1就可以得到代码的时间复杂度。

(1+2+3...+n+n)/ (n+1) = (n*(n+2))/2(n+1),那么平均时间复杂度为O(n)。

1+2+3...+n  可以推导出公式 n(n+1)/2,详细推导过程不明白的可以自己网上查查资料。

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:day22 模块-collections,time,random,pickle,shelve等

下一篇:初次安装python教程