更多优质内容
请关注公众号

数据结构与算法python语言实现(一)  算法分析-张柏沛IT博客

正文内容

数据结构与算法python语言实现(一) 算法分析

栏目:Python 系列:数据结构与算法python语言实现系列 发布时间:2020-05-17 23:46 浏览量:2362

分析算法的好坏主要是从计算机资源消耗的角度来评判的

如果一个算法能更高效的利用计算资源,或者更少的占用计算机资源就是更好的算法。


这里说的计算机资源是指:
1.存储空间(内存空间和辅存空间)
2.执行时间

如果要测试一个算法,请在一台机器上运行,因为一个相同的算法,放在不能性能的机器上运行得到的运行时间是不同的。

====================

大O表示法

大O表示法是用于衡量算法运行时间的。

怎么衡量一个算法的运行时间,或者说是什么使得一个算法的运行时间增加?
答案是赋值语句的数量。

一条赋值语句包含了(表达式)计算和(变量)存储这两个基本资源。
里面的计算就会消耗CPU资源,会消耗时间;
里面的存储就会消耗内存资源,会消耗空间;


例如一个累加的计算,我用两种算法实现

def sumOfN(n):
    res = 0
    for i in range(1,1+n):
        res+=i 
    
    return res
    
def sumofN2(n):
    res=0
    res = (n+1)*n/2
    return res 


    
假如我传入n=1000

此时算法1的赋值语句一共有 n+1 条
而  算法2的赋值语句只有 2 条

所以 算法1赋值语句数量用 T(n)=1+n 表示
     算法2赋值语句数量用 T(n)=2   表示
     

另一个概念 :问题规模
什么是问题规模,问题规模就是 n 。说更直白一点就是 上面的两个函数 我如果将 n=1000 改为 n=10000 那么就是将问题规模扩大。

算法分析的目标就是找出问题规模n会怎么影响一个算法的执行时间T(n)。
例如:算法1中,随着n的增大,T(n)会线性的增大
      算法2中,随着n的增大,T(n)不会增大
      
问题规模是影响运行时间的主导因素


除了问题规模,具体数据也是运行时间的影响因素
举个例子:
排序
如果我给一个完全打乱的数据集排序,和给一个只有一两个数是打乱的数据集排序,两个数据集的数据个数相同。此时用相同的算法排序后者会快于前者。

所以在实际测试中,我们应该设置多组数据,并且以多组数据的平均值作为比较的指标

大O表示法:
我们比较算法的好坏实际上不是看 T(n) 的值,而是看 T(n) 中起决定因素的主导部分。这个部分我们称之为 “数量级函数”,这个主导部分具体是什么?是T(n)中随着n增加而增加的最快的部分。

举例:
T(n)=1+n 
随着n增大,常数1会显得无足轻重,n才是主要部分,所以运行时间数量级是 O(n)

T(n)=5n^2+27n+1005
随着n增加,n^2的增长速度会越来越快,而27n+1005影响不大,系数5也是。所以主导部分是n^2 
数量级(函数)是 O(n^2)

也就是说:
数量级函数就是 T(n)中导数最大的那一项再去掉系数

下面是最常见的数量级

O(1)
O(logn)
O(n)
O(n*logn)
O(n^2)
O(n^3)
O(2^n)

上面7个数量级依次增加下面我们具体计算一个代码的时间复杂度

a=5
b=6
c=10    # 3次

for i in range(n):
    for j in range(n):
        x=i*i
        y=j*j 
        z=j*i               #3*n^2 次
        
for k in range(n):          
    w = a*k+45
    v = b*b                 # 2*n次

d=33        # 1次

所以 T(n) = 3n^2+2n+4 , O(n) = n^2

总结:
使用程序运行的时间衡量算法的好坏,而程序运行的时间由代码中赋值语句条数T(n)决定。
运行的时间由问题规模和具体数据决定,问题规模n是主要因素
现实中,使用T(n)中的主导部分O(xx)来表示时间复杂度,而不是T(n)本身。

================================

变位词判断问题

这样的词是变位词:长度相等,字母相同,排列顺序不同。
例如 heart earth ; python typhon 

接下来要使用4中算法来判断两个词是否为变位词

# 算法1:逐字检查法
# T(n)=(n+1)n/2  复杂度为 O(n^2)

def solution1(s1,s2):
    pos1 = 0
    s2 = list(s2)
    real_found = True
    while pos1<len(s1) and real_found:
        pos2 = 0
        found = False
        while pos2<len(s2) and not found:
            if s1[pos1] == s2[pos2]:
                s2[pos2] = None
                found = True
            else:
                pos2 += 1
        if not found:
            real_found = False

        pos1+=1

    return real_found

 

# 算法2:排序比较,即将两个单词按字母排序,之后再注意比较
# 复杂度为 O(nlogn),数量级的主导部分在sort()排序里面,sort后面的for循环复杂度为 n < nlogn ,所以复杂度为 O(nlogn)而不是O(n)

def solution2(s1,s2):
    len1 = len(s1)
    len2 = len(s2)

    if len1 != len2:
        return False

    s1 = list(s1)
    s2 = list(s2)
    s1.sort()
    s2.sort()

    for i in range(len1):
        if s1[i]!=s2[i]:
            return False

    return True

 

# 算法3:暴力法
# 列出s1所有字母能组成的单词的排列组合放到一个列表中
# 再循环判断s2是不是在 s1的字母组成的单词列表中
# 复杂度为 O(n!) 即n阶乘,它的数量级比2^n还要大

 

# 算法4:计数比较法,将单词的每个字母做一个计数器,将s1的计数器和s2的计数器进行比较
# T(n) = 2n+26 , 复杂度为 O(n)

def solution4(s1,s2):
    if len(s1) != len(s2):
        return False

    count1 = [0]*26
    count2 = [0]*26

    for alpha in s1:
        index = ord(alpha) - ord("a")
        count1[index]+=1

    for alpha in s2:
        index = ord(alpha) - ord("a")
        count2[index] += 1

    for i in range(len(count1)):
        if count1[i]!=count2[i]:
            return False

    return True

if __name__=="__main__":
    s1="python"
    s2="typhon"
    print(solution1(s1,s2))
    print(solution2(s1,s2))
    print(solution4(s1,s2))

  
综上:算法4复杂度最小,性能最优。
但是,注意观察,算法4使用了26长度的列表来保存计数器。是牺牲了存储空间换来的运算时间。

所以在算法中,经常会出现这种时间空间之间的取舍问题。


=====================================

python中两种内置数据类型list和dict的大O数量级

先说列表:
v=a[i] 或者 a[i]=v   -> O(1)
a.append(x)         -> O(1)    
list2 = list1 + [1,2,3]  -> O(n+k)

pop()       -> O(1)
pop(1)      -> O(n)

为什么pop传参和不传参它的复杂度不同?
原因是:pop(n) 需要将被移除元素后面的元素全部往前挪位复制一遍。
这个方法看起来很笨,但是他可以保证列表按索引取值赋值(a[i]=v, v=a[i])操作达到O(i)。
所以其实他是为了降低不常用操作的性能来提高常用操作的性能。

判断一个值是否在list中 (如 if v in list1) 性能是 O(n)


字典和列表不同,是根据关键码key 找到数据项,而列表式根据位置 index
对于字典而言,赋值和取值性能为 O(1)
而判断一个key是否在字典中(如 if k in dict1或者contains方法)性能也是O(1)




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 数据结构与算法python语言实现(一) 算法分析

热门推荐
推荐新闻