第二课：算法效率量化方法 -- 提升你的代码性能

第二课：算法效率量化方法 -- 提升你的代码性能

引用

CSDN

1.

https://m.blog.csdn.net/qq_57179696/article/details/146258520

在编程世界中，算法效率是衡量程序性能的重要指标之一。选择合适的算法和数据结构，可以显著提升程序的运行效率。本文将深入探讨Python算法效率量化方法，包括大O表示法、timeit模块实战、Python常见操作时间复杂度表以及对比不同列表创建方式的耗时差异。

1. 大O表示法详解

1.1 什么是大O表示法？

大O表示法（Big-O notation）是一种用于描述算法时间复杂度或空间复杂度的数学符号。它表示随着输入规模n的增大，算法的运行时间或所需空间如何增长。大O表示法关注的是算法的渐进行为，主要描述的是当n很大时，算法的性能如何变化。

1.2 常见的大O复杂度

• O(1)：常数时间复杂度，无论输入规模如何变化，算法的运行时间都是常数。
• O(log n)：对数时间复杂度，算法的运行时间随输入规模的增加而以对数的速度增长。
• O(n)：线性时间复杂度，算法的运行时间与输入规模成线性关系。
• O(n log n)：线性对数时间复杂度，算法的运行时间与输入规模的线性对数成正比。
• O(n^2)：平方时间复杂度，算法的运行时间与输入规模的平方成正比。
• O(2^n)：指数时间复杂度，算法的运行时间以指数方式增长。

1.3 示例代码

以下是一个简单的线性搜索算法示例，其时间复杂度为O(n)：

def linear_search(_arr, _target):
    for _index, _value in enumerate(_arr):
        if _value == _target:
            return _index
    return -1

# 测试线性查找
arr = [4, 2, 9, 7, 5, 1]
target = 7
index = linear_search(arr, target)
print(f"目标元素 {target} 的索引是: {index}")

2. timeit模块实战

2.1 timeit模块介绍

timeit模块是Python标准库中的一个模块，用于测量小段代码的执行时间。它提供了timeit.timeit()和timeit.repeat()等函数，可以精确地测量代码片段的执行时间。

2.2 示例代码

以下是一个使用timeit模块测量不同列表创建方式耗时的示例：

import timeit

# 使用append方式创建列表
def test_append():
    li = []
    for i in range(10000):
        li.append(i)

# 使用+方式创建列表
def test_plus():
    li = []
    for i in range(10000):
        li = li + [i]

# 使用列表推导式创建列表
def test_list_comprehension():
    li = [i for i in range(10000)]

# 使用list(range())方式创建列表
def test_list_range():
    li = list(range(10000))

# 使用Timer类测量执行时间
timer_append = timeit.Timer('test_append()', 'from __main__ import test_append')
timer_plus = timeit.Timer('test_plus()', 'from __main__ import test_plus')
timer_list_comprehension = timeit.Timer('test_list_comprehension()', 'from __main__ import test_list_comprehension')
timer_list_range = timeit.Timer('test_list_range()', 'from __main__ import test_list_range')

print(f"append方式: {timer_append.timeit(1000)} seconds")
print(f"+ 方式: {timer_plus.timeit(1000)} seconds")
print(f"列表推导式方式: {timer_list_comprehension.timeit(1000)} seconds")
print(f"list(range()) 方式: {timer_list_range.timeit(1000)} seconds")

从结果中可以看出，list(range())方式创建列表的效率最高，其次是列表推导式和append方式，而使用+方式创建列表的效率最低。

3. Python常见操作时间复杂度表

总结

本文详细介绍了Python算法效率量化方法，包括大O表示法、timeit模块实战、Python常见操作时间复杂度表以及对比不同列表创建方式的耗时差异。通过掌握这些方法，你可以更好地分析和优化Python代码的性能，提升程序的运行效率。