关于算法的时间复杂度和空间复杂度的分析

时间：2024-10-28 08:01:36

由于最近开始准备蓝桥杯(python组)，开始对编程基础进行一些复习，当我发现蓝桥对大多数题目程序运行时间及大小有要求时，我知道我不得不考虑性能问题，而不是能跑就行????

写下这篇文章希望对其他同志有帮助吧

什么是算法的时间复杂度和空间复杂度

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。衡量不同算法的优劣，主要还是根据算法所占的空间和时间两个维度去考虑。一个问题总有无数种解决办法，对于同一个问题，我们可以使用不同的方法去解决，但使用不同算法所耗费的资源和时间不同。

世界上没有完全完美的东西，也没有最合适你的女孩，不存在既不消耗最多的时间，也不占用最多的空间的完美无瑕的程序，鱼和熊掌不可得兼，那么就需要我们从中去寻找一个平衡点，写出能出色解决问题的较为完美的代码。

时间维度

时间维度指执行当前算法所消耗的时间，通常用时间复杂度来描述，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。度量一个程序的执行时间通常有两种方法：

事后统计法

该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。

事前分析法

程序运行前，对算法进行估算。程序运行时所消耗的时间取决于：算法采用的策略、方法；编译产生的代码质量；问题的输入规模；计算机硬件执行的速度。

时间频度

程序执行所耗费的时间，从理论上是不能算出来的，必须实际运行测试才能知道。

一个算法中的语句执行次数称为语句频度或时间频度T(n)，它只是一个估计值，一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

时间复杂度

在计算机科学中，时间复杂度是一个描述算法运行时间如何随着输入数据规模变化的度量。它是对算法运行时间增长趋势的一种抽象表示。

在时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。如果想知道它变化时呈现什么规律时，需要引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

常见时间复杂度量级

O(1) - 常数时间复杂度

这种复杂度表示算法的运行时间不随输入数据的大小而改变。

def constant_time_function(x):  
    return x * 2  # 这是一个常数时间操作  
  
# 无论x的值是多少，这个函数都只需要一个固定的时间来完成

O(n) - 线性时间复杂度

这种复杂度表示算法的运行时间与输入数据的大小成正比。

def linear_time_function(arr):  
    total = 0  
    for num in arr:  # 遍历数组中的每个元素  
        total += num  # 这是一个常数时间操作  
    return total  
  
# 如果arr的长度为n，则这个函数需要n个时间单位来完成

O(n^2) - 二次时间复杂度

这种复杂度表示算法的运行时间与输入数据大小的平方成正比。

def linear_time_function(arr):  
    total = 0  
    for num in arr:  # 遍历数组中的每个元素  
        total += num  # 这是一个常数时间操作  
    return total  
  
# 如果arr的长度为n，则这个函数需要n个时间单位来完成

O(log n) - 对数时间复杂度

这种复杂度通常出现在基于分治的算法中，如二分查找。

def linear_time_function(arr):  
    total = 0  
    for num in arr:  # 遍历数组中的每个元素  
        total += num  # 这是一个常数时间操作  
    return total  
  
# 如果arr的长度为n，则这个函数需要n个时间单位来完成

O(n log n) - 线性对数时间复杂度

这种复杂度通常出现在排序算法中，如归并排序和快速排序（在平均情况下）。

 # 这个过程的时间复杂度为O(n log n)。快速排序也类似，通过选择一个基准元素并将数组分成两部分， 
# 然后递归地对两部分进行排序，其平均时间复杂度也是O(n log n)。
def merge_sort(lst):
    if len(lst) <= 1:
        return lst
​
    mid = len(lst) // 2
    left_half = merge_sort(lst[:mid])
    right_half = merge_sort(lst[mid:])
​
    return merge(left_half, right_half)
​
def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0
​
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
​
    merged += left[left_index:]
    merged += right[right_index:]
​
    return merged
​
lst = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(lst))  # 输出：[3, 9, 10, 27, 38, 43, 82]

O(2^n) - 指数时间复杂度

这种复杂度表示算法的运行时间随输入数据的大小呈指数级增长，通常出现在递归算法中，且没有适当的剪枝或记忆化。

def exponential_time_function(n):  
    if n == 0:  
        return 1  
    else:  
        return 2 * exponential_time_function(n - 1)  # 每次递归调用都会使问题规模减半，但总时间呈指数增长  
  
# 对于一个输入n，这个函数的时间复杂度为O(2^n)

空间复杂度

空间复杂度是对在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势

关于空间复杂度 S(n) 的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，空间复杂度并不是程序占用了多少bytes的空间，因为这个也没有太大意义，空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

常见空间复杂度

常数空间 O(1)*O*(1)：

空间需求是固定的，不随输入规模变化。例如，交换两个数的值：

def swap(a, b):
    temp = a
    a = b
    b = temp
    return a, b
​
print(swap(1, 2))  # 输出：(2, 1)

线性空间 O(n)*O*(*n*)：

空间需求与输入规模线性相关。例如，创建一个与输入规模大小相同的新列表：

def swap(a, b):
    temp = a
    a = b
    b = temp
    return a, b
​
print(swap(1, 2))  # 输出：(2, 1)

二次空间 O(n2)*O*(*n*2)：

空间需求与输入规模的平方成正比。例如，创建一个 n×nn×n 的二维数组：

def swap(a, b):
    temp = a
    a = b
    b = temp
    return a, b
​
print(swap(1, 2))  # 输出：(2, 1)

时间复杂度和空间复杂度的计算

时间复杂度计算

时间复杂度是衡量算法执行时间随输入数据规模增长而变化的快慢程度的指标。它通常表示为输入数据规模n的函数，即T(n)。算法的时间复杂度越低，表示它在处理大规模数据时所需的执行时间越短，效率越高。

识别基本操作：

  • 基本操作是算法中执行次数最多的操作，它通常是算法的核心部分，决定了算法的整体性能。

  • 在分析时，需要关注循环、递归等可能导致操作次数大量增加的部分。

计算执行次数：

  • 对于单层循环，执行次数通常是输入数据规模n的线性函数，即O(n)。

  • 对于嵌套循环，需要分别计算每一层循环的迭代次数，并将它们相乘得到总执行次数。例如，两层嵌套循环的执行次数通常为O(n^2)。

  • 对于递归算法，需要分析递归调用的次数和递归深度，以及每次递归调用中的操作次数。

应用大O表示法：

  • 大O表示法用于简化执行次数的表达式，只保留最高阶项，并忽略系数和常数项。这是因为当n足够大时，高阶项的增长速度将远远超过低阶项和常数项。

  • 例如，如果执行次数为3n2)。

考虑最坏情况：

  • 在分析时间复杂度时，通常考虑最坏情况，即输入数据使得算法执行时间最长的情况。这是因为最坏情况给出了算法性能的上界，有助于评估算法在最不利条件下的表现。

示例分析：

  • 线性搜索：在最坏情况下，需要遍历整个数组才能找到目标元素，因此时间复杂度为O(n)。

  • 二分搜索：在有序数组中查找元素时，每次将搜索范围减半，因此时间复杂度为O(log n)。

  • 冒泡排序：通过相邻元素的比较和交换进行排序，每趟排序都会将最大的元素移动到数组的末尾。在最坏情况下，需要进行n-1趟排序，每趟排序的比较次数为n-i（i为当前趟数），因此总时间复杂度为O(n^2)。

  • 归并排序：将数组分成两半分别排序，然后合并结果。每次合并的复杂度为O(n)，递归深度为log n，因此总时间复杂度为O(n log n)。

空间复杂度的计算

分析存储需求：

  • 包括算法中定义的局部变量、数组、链表、栈、队列等数据结构所占用的空间。

  • 注意区分输入数据所占用的空间和算法执行过程中产生的临时空间。输入数据所占用的空间通常不计入空间复杂度。

计算空间总量：

  • 根据算法的执行过程，计算所需存储空间的总量。这包括所有局部变量和临时数据结构所占用的空间。

  • 如果空间使用量与输入数据规模成正比，则空间复杂度为O(n)等。

应用大O表示法：

  • 与时间复杂度类似，使用大O表示法来简化空间总量的表达式。只保留最高阶项，并忽略系数和常数项。

考虑递归栈空间：

  • 对于递归算法，需要考虑递归栈的深度。递归栈空间用于存储递归调用过程中的局部变量和返回地址等信息。

  • 如果递归深度与输入数据规模成正比，则空间复杂度为O(n)。如果递归深度是固定的（如二分搜索），则空间复杂度为O(1)（不考虑系统栈空间）。

示例分析：

  • 常数空间：如果算法只使用固定数量的额外空间（如几个变量），则空间复杂度为O(1)。

  • 线性空间：如果算法使用与输入数据规模成正比的额外空间（如一个长度为n的数组），则空间复杂度为O(n)。

  • 递归空间：对于递归算法，如果递归深度与输入数据规模成正比（如递归求解斐波那契数列），则空间复杂度为O(n)。如果递归深度是固定的（如二分搜索），则空间复杂度为O(1)（不考虑系统栈空间）。但需要注意的是，在实际应用中，系统栈空间也是有限的，因此过深的递归可能会导致栈溢出错误。

写在最后：

区分不同情况：时间复杂度和空间复杂度通常考虑最坏情况，但也可以分析最好情况和平均情况。最好情况和平均情况可能给出更准确的算法性能评估，但在某些情况下（如在线算法或实时系统），最坏情况可能更为重要。

考虑常数项和系数：虽然大O表示法忽略了常数项和系数，但在实际应用中，它们可能对算法性能有显著影响。特别是在处理小规模数据时，低阶项和系数可能占据主导地位。因此，在评估算法性能时，需要综合考虑时间复杂度和空间复杂度以及常数项和系数的影响。

综合评估：在选择算法时，除了时间复杂度和空间复杂度外，还需要考虑算法的稳定性、可读性、可维护性等因素。一个优秀的算法应该在这些方面都有良好的表现。

相关文章