警惕时间复杂度陷阱
写在这里
一个bilibili视频也展示了这个：[bilibili视频][https://www.bilibili.com/video/bv16u4m1c7cu/?spm_id_from=333.999.0.0] 我觉得这是一个很好的视频，但它的语言是中文。
时间复杂度
- 时间复杂度是什么意思？
时间复杂度是算法运行所需时间的度量，作为其输入大小的函数。它是描述算法效率的一种方式，用于比较不同的算法并确定哪种算法最有效。
如何计算时间复杂度？
为了计算时间复杂度，我们需要将算法执行的操作数视为输入大小的函数。测量操作次数的最常见方法是计算特定操作执行的次数。
计算时间复杂度时有哪些常见陷阱？
- 不考虑输入大小：如果我们只考虑算法执行的操作数量，我们可能会低估时间复杂度。例如，如果我们计算循环运行的次数，但不考虑输入的大小，那么时间复杂度可能会太高。
- 不考虑算法的效率：有些算法即使输入量很小也可能会执行很多操作，这会导致时间复杂度很高。例如，冒泡排序和选择排序等排序算法具有二次时间复杂度，即使它们可能只需要交换小数组中的两个元素。
- 不考虑算法的最坏情况：某些算法具有最好情况，其中执行的操作比最坏情况要少。例如，像二分搜索这样的搜索算法有一个最好的情况，即它们在对数时间内找到目标元素，但它们有一个最坏的情况，即它们需要检查数组中的所有元素。
让我们看一些时间复杂度的例子
这里有一个问题：
找出列表中最多 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 <= 0:
return []
max_heap = []
for num in nums:
if len(max_heap) < n:
max_heap.append(num)
# call sift_down
for i in range((len(max_heap) - 2) // 2, -1, -1):
_sift_down(max_heap, i)
elif num > 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 < len(heap) and heap[left] > heap[largest]:
largest = left
if right < len(heap) and heap[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 <= 0:
return []
max_heap = []
for num in nums:
if len(max_heap) < n:
max_heap.append(num)
# call sift_down
for i in range((len(max_heap) - 2) // 2, -1, -1):
_sift_down(max_heap, i)
elif num > 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 < len(heap) and heap[left] > heap[largest]:
largest = left
if right < len(heap) and heap[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 不大
使用heapq：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.00012412450001668184996
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
使用heapq：0.0014836000045761466
python 堆：10.537632800056599
排序：0.0012236000038683414
n = 12000
使用heapq：0.001384599949233234
python 堆：12.328411899972707
排序：0.0013226999435573816
n = 13000
使用heapq：0.0020017001079395413
python 堆：15.637207800056785
排序：0.0015075999544933438
n = 14000
使用heapq：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官方文档。
bulit-in 函数比 heapq 更快，因为它是用 c 编写的，c 是一种编译语言。
- 如何改善？
- 您可以使用内置函数sorted()代替heapq.sort()来提高代码的性能。 sorted() 函数是 python 中的内置函数，它是用 c 实现的，因此比 heapq.sort() 快得多
脑震荡
当我们处理大数据时，我们应该使用内置函数而不是 heapq.sort() 来提高代码的性能。在处理大数据时，我们必须警惕时间复杂度陷阱。有时时间复杂度陷阱是不可避免的，但我们应该尽量避免它们。
关于我
大家好，我是梦沁园。我是一名学生。我喜欢学习新事物。
你可以看我的github：[mengqinyuan的github][https://github.com/mengqinyuan]
