Python 算法基础篇：时间复杂度和空间复杂度简介

小蓝枣

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

6260

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

文章被收录于专栏：CSDN博客专家-小蓝枣的博客

Python 算法基础篇：时间复杂度和空间复杂度简介

引言

在学习和分析算法时，时间复杂度和空间复杂度是两个关键概念。它们帮助我们评估算法的性能和资源使用情况。本篇博客将为你介绍时间复杂度和空间复杂度的概念，并通过 Python 示例代码演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 时间复杂度

时间复杂度是衡量算法运行时间随输入规模增长的增长率。它表示了算法的时间开销，即算法运行所需的时间。时间复杂度通常使用大 O 符号表示法来表示。

a ) 常见的时间复杂度

常见的时间复杂度有以下几种：

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

b ) 时间复杂度示例

下面通过几个示例来演示时间复杂度的应用：

示例 1 ：计算列表元素的和

def sum_of_list(lst):
    sum = 0
    for num in lst:
        sum += num
    return sum

# 示例使用
nums = [1, 2, 3, 4, 5]
result = sum_of_list(nums)
print("列表元素的和：", result)

代码解释：上述代码定义了一个 sum_of_list 函数，它接受一个列表 lst 作为输入，并使用 for 循环计算列表元素的和。该算法的时间复杂度是 O ( n )，因为它需要遍历整个列表。

示例 2 ：二分查找算法

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

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

代码解释：上述代码定义了一个 binary_search 函数，它使用二分查找算法在有序列表 arr 中查找目标元素 target 。该算法的时间复杂度是 O ( log n )，因为每次迭代都将问题的规模减半。

通过上述示例，我们可以看到不同算法的时间复杂度如何随着输入规模的增长而变化。理解算法的时间复杂度可以帮助我们选择合适的算法来解决问题，并评估算法的性能。

2. 空间复杂度

空间复杂度是衡量算法所需的额外空间随输入规模增长的增长率。它表示了算法所需的额外内存空间。空间复杂度通常使用大 O 符号表示法来表示。

a ) 常见的空间复杂度

常见的空间复杂度有以下几种：

O ( 1 )：常数空间复杂度，表示算法所需的额外空间是固定的。
O ( n )：线性空间复杂度，表示算法所需的额外空间与输入规模成线性关系。
O ( n ^ 2 )：平方空间复杂度，表示算法所需的额外空间与输入规模的平方成正比。

b ) 空间复杂度示例

下面通过几个示例来演示空间复杂度的应用：

示例 1 ：生成斐波那契数列

def fibonacci(n):
    fib = [0, 1]
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    return fib[n]

# 示例使用
num = 10
result = fibonacci(num)
print("斐波那契数列的第 {} 个数是：{}".format(num, result))

代码解释：上述代码定义了一个 fibonacci 函数，它接受一个正整数 n 作为输入，并生成斐波那契数列中第 n 个数。该算法的空间复杂度是 O ( n )，因为它需要存储整个斐波那契数列。

示例 2 ：递归算法

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

# 示例使用
num = 5
result = factorial(num)
print("{} 的阶乘是：{}".format(num, result))

代码解释：上述代码定义了一个 factorial 函数，它使用递归方式计算正整数 n 的阶乘。该算法的空间复杂度是 O ( n )，因为每次递归调用都需要在内存中保存函数的调用栈。