Python实现程序运行时间度量分析

男娘i 2023-06-29 10:59 13阅读 0赞

*  推荐自己的专栏：[分享一些Python案例，将所学用出来][Python]

--------------------

# **一：算法时间复杂度分析函数的设计** #

*  程序的运行时间长度与算法的设计和所求解的问题的规模有关。
 *  当输入大小(即问题规模)增大时，程序的运行时间递增比例，即是算法的时间复杂度。

设计思路如下:

1.  定义函数buildData(n)，构造并返回规模为n的测试输入数据。例如，排序随机n个数的列表。

def buildData(n):
        """构造测试规模为n的输入数据,对于排序，随机n个数的列表"""
        data = [random.randrange(n) for i in range(n)]
        return data

1.  定义函数timing(f, data)， 返回调用f(data)的运行时间。

def timing(f, data):
        """测量函数调用f(data)的运行时间分析"""
        start = time.time() #记录开始时间
        f(data)  #运行f(data)
        end = time.time()  #记录结束时间
        return end - start #返回执行时间

1.  定义函数timingAnalysis(f, m1, m2, runs, buildData)， 测量并输出**函数** **f** 在不同输入规模: 10m1、10m1\+1、 …、10m2 情况下运行runs次的平均时间。  
    函数调用buildData(n)规模为n的数据data，然后调用timing(f, data) 测量函数的运行时间。

def timingAnalysis(f,m1, m2, runs, buildData) :
        """输出函数f在不同输入规模: 10**m1,.... ,10**m2运行runs次的时间"""
        for n in [10**i for i in range(m1, m2+1)]:  #10**m1,...，10**m2
              data = buildData (n)
              total = 0.0  #初始化总时间
              for i in range(runs) : #重复运行runs次
                  total += timing(f, data) #运行f并累计运行时间
              strResult = '输入规模{:10}时函数{:15}运行{}次的平均时间为: {} 秒'
              print (strResult.format(n, f.__name__, runs, total/runs))

1.  在测试代码中，导入各种排序算法（不在本篇文章中赘述，有兴趣者可以下载完整代码查看），然后调用分析各排序算法的时间复杂度。

# **二：算法时间复杂度分析函数的实现与应用** #

**time\_analysis.py**

import time
    import random
    
    def timing(f, data):
        """测量函数调用f(data)的运行时间分析"""
        start = time.time() #记录开始时间
        f(data)  #运行f(data)
        end = time.time()  #记录结束时间
        return end - start #返回执行时间
    
    def timingAnalysis(f,m1, m2, runs, buildData) :
        """输出函数f在不同输入规模: 10**m1,.... ,10**m2运行runs次的时间"""
        for n in [10**i for i in range(m1, m2+1)]:  #10**m1,...，10**m2
              data = buildData (n)
              total = 0.0  #初始化总时间
              for i in range(runs) : #重复运行runs次
                  total += timing(f, data) #运行f并累计运行时间
              strResult = '输入规模{:10}时函数{:15}运行{}次的平均时间为: {} 秒'
              print (strResult.format(n, f.__name__, runs, total/runs))
    
    def buildData(n):
        """构造测试规模为n的输入数据,对于排序，随机n个数的列表"""
        data = [random.randrange(n) for i in range(n)]
        return data
    
    
    #测试代码
    
    if __name__ ==  "__main__" :
        from bubbleSort import bubbleSort
        from selectionSort import selectionSort
        from insertSort import insertSort
        from mergeSort import mergeSort
        from quickSort import quickSort
    
        def quickSort1 (a) :
            quickSort(a, 0, len(a) - 1)
    
        #冒泡排序算法，时间复杂度分析
        timingAnalysis (bubbleSort, 2, 4, 1, buildData)
        print()
    
        #选择排序算法，时间复杂度分析
        timingAnalysis (selectionSort, 2, 4, 1, buildData)
        print()
    
        #插入排序算法，时间复杂度分析
        timingAnalysis (insertSort, 2, 4, 1, buildData)
        print()
    
        #归并排序算法，时间复杂度分析
        timingAnalysis (mergeSort, 1, 4, 1, buildData)
        print()
    
        #快速排序算法，时间复杂度分析
        timingAnalysis (quickSort1, 1, 4, 1, buildData)
        print()
    
        #内置排序算法sort，时间复杂度分析
        timingAnalysis(sorted, 1, 4, 1, buildData)

运行：

输入规模       100时函数bubbleSort     运行1次的平均时间为: 0.000997781753540039 秒
    输入规模      1000时函数bubbleSort     运行1次的平均时间为: 0.10474658012390137 秒
    输入规模     10000时函数bubbleSort     运行1次的平均时间为: 8.514265298843384 秒
    
    输入规模       100时函数selectionSort  运行1次的平均时间为: 0.0 秒
    输入规模      1000时函数selectionSort  运行1次的平均时间为: 0.044878244400024414 秒
    输入规模     10000时函数selectionSort  运行1次的平均时间为: 4.592764377593994 秒
    
    输入规模       100时函数insertSort     运行1次的平均时间为: 0.0009894371032714844 秒
    输入规模      1000时函数insertSort     运行1次的平均时间为: 0.0917809009552002 秒
    输入规模     10000时函数insertSort     运行1次的平均时间为: 7.810081720352173 秒
    
    输入规模        10时函数mergeSort      运行1次的平均时间为: 0.0 秒
    输入规模       100时函数mergeSort      运行1次的平均时间为: 0.000997304916381836 秒
    输入规模      1000时函数mergeSort      运行1次的平均时间为: 0.0029914379119873047 秒
    输入规模     10000时函数mergeSort      运行1次的平均时间为: 0.03091740608215332 秒
    
    输入规模        10时函数quickSort1     运行1次的平均时间为: 0.0 秒
    输入规模       100时函数quickSort1     运行1次的平均时间为: 0.0009975433349609375 秒
    输入规模      1000时函数quickSort1     运行1次的平均时间为: 0.001994609832763672 秒
    输入规模     10000时函数quickSort1     运行1次的平均时间为: 0.02396249771118164 秒
    
    输入规模        10时函数sorted         运行1次的平均时间为: 0.0 秒
    输入规模       100时函数sorted         运行1次的平均时间为: 0.0 秒
    输入规模      1000时函数sorted         运行1次的平均时间为: 0.0 秒
    输入规模     10000时函数sorted         运行1次的平均时间为: 0.0019676685333251953 秒

[Python]: https://blog.csdn.net/zhangguohao666/category_9939572.html