警惕时间复杂度陷阱

写在这里

bilibili视频也显示了这个：[Bilibili视频][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0]我认为这是一个很好的视频，但它的语言是中文。

时间复杂度

• 时间复杂度是什么意思？

• 时间复杂度是算法运行所需时间的度量，作为其输入大小的函数。它是描述算法效率的一种方式，用于比较不同的算法并确定哪种算法最有效。

• 如何计算时间复杂度？

• 为了计算时间复杂度，我们需要考虑算法执行的操作数作为输入大小的函数。测量操作次数的最常见方法是计算执行特定操作的次数。

• 计算时间复杂度时有哪些常见陷阱？

• 1. 不考虑输入大小：如果我们只考虑算法执行的操作数量，我们可能会低估时间复杂度。例如，如果我们计算循环运行的次数，但不考虑输入的大小，那么时间复杂度可能会太高。
• 1. 不考虑算法的效率：有些算法即使输入量很小也可能执行很多操作，这可能导致时间复杂度很高。例如，冒泡排序和选择排序等排序算法具有二次时间复杂度，即使它们可能只需要交换小数组中的两个元素。
• 1. 不考虑算法的最坏情况：某些算法具有最好情况，其中执行的操作比最坏情况要少。例如，像二分搜索这样的搜索算法有一个最好的情况，即它们在对数时间内找到目标元素，但它们有一个最坏的情况，即它们需要检查数组中的所有元素。

让我们看一些时间复杂度的例子

这里有一个问题：
查找列表中最多 10 个整数。

import random
ls = [random.randint(1, 100) for _ in range(n)]

这里是测试函数：

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

解决方案1：使用堆

这是使用heapq模块的解决方案：

def find_max_n(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

或者我们用python的方式写：

def find_largest_n(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)

解决方案2：使用排序

这里是使用排序功能的解决方案：

def find_max_n(ls, n):
    return sorted(ls, reverse=True)[:n]

几乎所有人都知道，堆的时间复杂度是 O(n log k)，排序函数的时间复杂度是 O(n log n)。

看来第一个解决方案比第二个更好。但在Python中却并非如此。

看最终代码：

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

def find_max_n_heapq(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

def find_max_n_python_heap(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)


def find_max_n_sorted(ls, n):
    return sorted(ls, reverse=True)[:n]

# test
import random
for n in range(10, 10000, 100):
    ls = [random.randint(1, 100) for _ in range(n)]
    print(f"n = {n}")
    print(f"Use    Heapq: {benchmark(find_max_n_heapq, ls, n)}")
    print(f"Python Heapq: {benchmark(find_max_n_python_heap, ls, n)}")
    print(f"Sorted      : {benchmark(find_max_n_sorted, ls, n)}")

我在Python3.11 VScode中运行，结果如下：

n 不大

使用堆：0.002430099993944168
Python堆：0.06343129999004304
排序：9.280000813305378e-05
n = 910
使用堆：9.220000356435776e-05
Python堆：0.07715500006452203
排序：9.360001422464848e-05
n = 920
使用堆：9.440002031624317e-05
Python堆：0.06573969998862594
排序：0.00012450001668184996
n = 930
使用堆：9.689992293715477e-05
Python堆：0.06760239996947348
已排序：9.66999214142561e-05
n = 940
使用堆：9.600003249943256e-05
Python堆：0.07372559991199523
排序：9.680003859102726e-05
n = 950
使用堆：9.770004544407129e-05
Python堆：0.07306570000946522
排序：0.00011979998089373112
n = 960
使用堆：9.980006143450737e-05
Python堆：0.0771204000338912
排序：0.00022829999215900898
n = 970
使用堆：0.0001601999392732978
Python堆：0.07493270002305508
排序：0.00010840001050382853
n = 980
使用堆：9.949994273483753e-05
Python 堆：0.07698320003692061
排序：0.00010300008580088615
n = 990
使用堆：9.979994501918554e-05
Python堆：0.0848745999392122
排序：0.00012620002962648869

如果n很大？

n = 10000
使用堆：0.003642000025138259
Python 堆：9.698883199947886
排序：0.00107999995816499
n = 11000
使用堆：0.0014836000045761466
Python 堆：10.537632800056599
排序：0.0012236000038683414
n = 12000
使用堆：0.001384599949233234
Python 堆：12.328411899972707
排序：0.0013226999435573816
n = 13000
使用堆：0.0020017001079395413
Python 堆：15.637207800056785
排序：0.0015075999544933438
n = 14000
使用堆：0.0017026999266818166
Python 堆：17.298848500009626
排序：0.0016967999981716275
n = 15000
使用堆：0.0017773000290617347
Python 堆：20.780625900020823
排序：0.0017105999868363142

我发现了什么以及如何改进它

当n很大时，Sorted会花费一点时间（有时甚至比使用heapq更好），但Python Heapq会花费很多时间。

• 为什么Sorted花费一点时间，而Python Heapq花费很多时间？
• 因为sorted()是Python中的内置函数，所以你可以找到关于它的Python官方文档。

内置函数比 heapq 更快，因为它是用 C 编写的，C 是一种编译语言。

• 如何改进？
• 您可以使用内置函数sorted()代替heapq.sort()来提高代码的性能。 Sorted() 函数是 Python 中的内置函数，它是用 C 实现的，因此比 heapq.sort()
快得多

脑震荡

当我们处理大数据时，我们应该使用内置函数而不是 heapq.sort() 来提高代码的性能。在处理大数据时，我们必须警惕时间复杂度陷阱。有时时间复杂度的陷阱是不可避免的，但我们应该尽量避免它们。

关于我

大家好，我是梦沁园。我是一名学生。我喜欢学习新事物。
你可以看我的github：[MengQinYuan的Github][https://github.com/mengqinyuan]