Python 算法基础篇：大O符号表示法和常见时间复杂度分析

小蓝枣

发布于 2023-07-24 15:05:04

4060

发布于 2023-07-24 15:05:04

Python 算法基础篇：大 O 符号表示法和常见时间复杂度分析

引言

在分析和比较算法的性能时，时间复杂度是一项重要的指标。而大 O 符号表示法是用来描述算法时间复杂度的常见表示方法。本篇博客将为你介绍大 O 符号表示法的概念以及常见的时间复杂度分析，同时通过 Python 代码示例来演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 大 O 符号表示法

大 O 符号表示法是一种用来描述算法时间复杂度的记号系统。它表示算法运行时间随输入规模增长的上界。在大 O 符号表示法中，我们通常关注算法的最坏情况下的运行时间。

a ) 大 O 符号的定义

大 O 符号表示法的定义如下：

O ( g ( n ))：表示算法的时间复杂度为 g ( n )。
g ( n )：表示一个函数，表示算法的运行时间。
n ：表示输入规模的大小。

在大 O 符号表示法中，常见的函数有以下几种：

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

b ) 示例代码

下面通过几个示例来演示大 O 符号表示法的应用：

示例 1 ：线性搜索算法

def linear_search(arr, target):
    for i, num in enumerate(arr):
        if num == target:
            return i
    return -1

# 示例使用
arr = [4, 2, 9, 7, 5, 1]
target = 7
index = linear_search(arr, target)
print("目标元素 {} 的索引是：{}".format(target, index))

代码解释：上述代码定义了一个 linear_search 函数，它接受一个列表 arr 和目标元素 target 作为输入。函数使用 for 循环逐个查找列表中的元素，如果找到目标元素，则返回其索引，否则返回- 1 。该算法的时间复杂度是 O ( n )，因为它需要遍历整个列表。

示例 2 ：快速排序算法

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

# 示例使用
arr = [4, 2, 9, 7, 5, 1]
sorted_arr = quick_sort(arr)
print("排序后的列表：", sorted_arr)

代码解释：上述代码定义了一个 quick_sort 函数，它使用递归的方式实现快速排序算法。函数首先选择一个基准元素 pivot ，然后将列表分割为比基准元素小和大的两个子列表。最后，通过递归调用 quick_sort 函数对子列表进行排序，并将结果合并返回。该算法的时间复杂度是 O ( n log n )，因为每次递归调用都将问题的规模减半。