python数据结构学习笔记-2016-10-21-01-复杂度分析

        程序执行时间取决于以下几个因素:

  • 数据量;
  • 硬件类型和执行时刻,关于执行时刻,按书中说是是否有其他程序在同时运行;
  • 编程语言和编译器也是一大关键因素。
        4.1 复杂度分析

        评价一个算法的效率,可以数逻辑比较、数据交换以及算术运算的数目。

        比如说计算n×n矩阵的所有数值之和。

>>> totalSum = 0
>>> for i in range(n):
...     rowSum[i] = 0
...     for j in range(n):
...         rowSum[i] += matrix[i, j]
...         totalSum += matrix[i, j]

        在这一算法中,在内循环中,可以看到加法的执行次数是2,外循环没有执行加法,所以内外两个循环总共是执行了2n²次加法。

>>> totalSum = 0
>>> for i in range(n):
...     rowSum[i] = 0
...     for j in range(n):
...         rowSum[i] += matrix[i, j]
...     totalSum += rowSum[i]
       在这一算法中,在内循环中,加法的执行次数是1,外循环中的执行次数也是1,所以总共执行n²+n次加法。

       上述两个算法,在n数值较大时,基本上都是以n²数量级的执行次数。

       4.1.1 大O表示法

       对于一个算法,其步骤执行数为T(n),n是数据量,则若存在正整数m和常数c,使得当n>m时,T(n)

       注意f(n)必须是最大上限。c被称为比例常数。

       当两个算法有相同的时间复杂度时,比例常数c就成为比较关键的因素。

       常数时间(constant time),是指程序执行基本操作所需时间,对应O(1)。

       主项(dominant term):是影响时间复杂度的主要因素。例如,一个算法的步骤执行次数是n²+log₂n+3n,显然其受n²项影响最大。

       算法分类

f(n) 名称
1 常数(constant)
log n 对数级(logarithmic)
n 线性级(linear)
n log n 线性对数级(log linear)
平方级(quadratic)
立方级(cubic)
aⁿ 指数级(exponential)

       
      4.1.2 评价python代码

      基本操作(basic operation):不依赖于特定数值的语句和函数调用。基本操作的时间复杂度是O(1)。

      比如说

>>> x = 5
      就是基本操作。
 
>>> y = x
>>> z = x + y * 6
>>> done = x > 0 and x < 100
     这些也都是基本操作。


     线性级例子 O(n)

>>> def ex1( n ):
...     total = 0
...     for i in range( n ) :
...         total += i
...     return total
     

     平方级例子 O(n²) (在嵌套循环中多见,但不是所有嵌套循环都是平方级)

>>> def ex3( n ):
...     count = 0
...     for i in range( n ) :
...         for j in range( n ) :
...             count += 1
...     return count
      
      对数级例子 O(log n)

>>> def ex6( n ):
...     count = 0
...     i = n
...     while i >= 1 :
...         count += 1
...         i /= 2
...     return count

      线性对数级例子 O(n log n)

>>> def ex7( n ):
...     count = 0
...     for i in range( n )
...         count += ex6( n )
        return count


     不同情况

     执行以下代码

>>> def findNeg( intList ):
...     n = len(intList)
...     for i in range( n ) :
...         if intList[i] < 0 :
...             return i
...     return None

     如果是以下情况,显然程序的时间复杂度是O(n),因为要将列表中所有元素都遍历,这被称之为最坏情况(worst case)。

>>> L = [ 72, 4, 90, 56, 12, 67, 43, 17, 2, 86, 33 ]
>>> p = findNeg( L )
     如果是以下情况,显然程序只需遍历一次即可,这被称之为最好情况(best case)。
>>> L = [ -12, 50, 4, 67, 39, 22, 43, 2, 17, 28 ]
>>> p = findNeg( L )
     介于两者之间的称为平均情况,是我们执行算法时碰到的大多数情况。

     但衡量一个算法的效率,还是要看最坏情况。

你可能感兴趣的