利用Python浅尝算法分析

引言

学习编程的人或许都听说过,程序 = 数据结构 + 算法 .数据是程序的中心,算法是解决问题的步骤,数据结构和算法两个概念间的逻辑关系贯穿了整个程序世界，首先二者表现为不可分割的关系.没有数据间的有机关系，程序根本无法设计。数据结构是底层，算法是上层。数据结构为算法提供服务,算法围绕数据结构进行操作

这些概念较为抽象,我们浅尝辄止,本文只介绍一些简单的理论,我们平时练习的程序可能运算规模和数据规模都很小每次运行都能很快得出结果,可以说是秒出.因为现在计算机技术的快速发展,就算是个人计算机一样有这非常可观的算力.但是这并不能改变运行程序时消耗资源的事实.

在实际的开发中,无论是设计还是应用一种算法,我们都要了解这种算法的性能如何,通常我们在衡量一个算法的性能时关心的是对 CPU 和内存的使用率,但是 CPU 是计算机中最为珍贵的资源,我们还是以 CPU 的使用率为主,它体现在算法上就是算法的运算速度,用一个专业的描述就是算法的时间复杂度.相应,如果要计算的是程序运行需要的空间需要考虑的就是空间复杂度.作为上层的使用者我们更关心是时间复杂度,时间越快越好,但是资源开销的成本来看,我们会平衡时间和空间进行取舍.

什么是时间复杂度

不同机器运算速度不一样，我们如何统一衡量一个算法的执行时间呢？计算机科学家们想到，可以用计算步骤来称量。我们所说的算法时间复杂度一般就是指解决问题所执行的语句频数.即算法从开始执行到执行完毕所需要的步骤数量。说通俗点,就是计算程序运行步骤次数的最高阶.由于并不是每个算法都能上机测试,而且现实中也没有太大的必要,我们一般需要分析得出大致计算所需要的资源,才会上机,而不是盲目上机测试.说白了.我们使用算法中语句的执行次数对算法进行估算,哪个算法中语句执行次数多,它花费的时间就多,同时我们通常将算法中的语句执行次数称为时间频度,记为 T(n),n 表示的是语句的规模

什么是大 O 表示法

有了 T(n)之后,还有一个问题就是我们不知道随着处理数据的的增长他的变化会呈现出什么规律,因此引入辅助函数 f(n)的概念,他和 T(n)是同一个量级的,使用符号 O(f(n))来替代 T(n).O(f(n))这种形式也称为大 O 表示法.这样我们可以使用函数分析的手段较为准确地分析时间频度 T(n),并以此来计算时间复杂度

大 O 表示法的规则

有些运行处理对于当前的算法来说影响很小,几乎可以忽略不计.

大 O 表示法的简单规则如下:

1. 常数项使用 O(1)表示
2. 高阶因子和低阶因子并存,只保留高阶因子
3. 如果高阶因子项存在并且不是常数项,则去除系数

对与上面的描述你可能还有一点一知半解,那我们就通过例子来唠一唠

算法分析的简单小实例:

常数阶:比如我们平时一些简单的赋值.简单的四则运行

a = 2
b = 5
c = 0.5*a*b
print(c)

上面的例子所有语句最高阶是 1,是常数级的.所以他们整体就是常数级的,所以他的时间复杂度就是常数阶用 O(1)表示;不管这样的语句有多少条,时间复杂度也不会变,在算法中常数阶也是运行速度最快的

线性阶:简单理解就是可能涉及到单层循环

for i in range(n):
  print('hello!')
  

因为循环体中的时间复杂度为 O(1)常数阶的代码执行了 n 次,这段代码的规模就是由 n 的大小决定的.所以它的时间复杂度为 O(n)

平方阶:简单理解是在线性阶的基础上由多加了一层循环

for i in range(n):
  for j in range(m):
    print('你好')

在这段代码中最里层代码依然是常数阶,常数阶外面为两层循环,内层循环的频数是由外层决定的,所以,它的时间复杂度不能简单地设为 n^2.但是我们可以对其进行推导,代码中输出语句执行的次数为:n+(n-1)+(n-2)+······+1 这是一个等差数列,由等差数列公式可得该式为 n^2+n/2.根据上文中大 O 表示法的第 2 和 3 条规则可得出最高阶为 n^2,所以上面代码的时间复杂度为 O(n^2)

常见时间复杂度的比较

下面分别从简单的例子列举中了解常用的算法复杂度:

O(1):从一个数据集中获取第一个元素

l = [1,2,3,4]
first = l[0]
print(first)

O(log n):将数据集分为两堆,然后将分好的部分再分半,以此类推(二分法)

def binary_search(list, item):
    low = 0
    high = len(list)-1                         
    n = 0
    while low <= high:
        mid = int((low + high)/2)              

        guess = list[mid]
        n += 1

        if list[mid]==item:
            print(n)
            return mid

        if list[mid]<item:                    
            low = mid + 1
        else:
            high = (mid-1)
    return None
 
l=[1,2,3,4,8,9,11,12,14,18,19,20,28]
print(binary_search(l,12))

O(n):遍历一个数据集

l = [1,2,3,4]
for i in l:
  print(i)

O(n log n):给数据生成所有的排列组合同时遍历分出来的每一半数据

O(n^2)平方级:遍历一个数据集中的每个元素的同时遍历另一个同数量级的数据集

O(2^n)指数级:为一个数据集生成其可能的所有子集

O(n!)阶乘级:给数据集生成所有的排列组合

唠一唠:你那些常用的算法都分别对应着上面的哪种时间复杂度呢?