时间复杂度最小数组数

Question

我刚开始学习Python中的数据结构和算法，遇到了以下问题：

"编写两个 Python 函数来查找列表中的最小数字。第一个函数应将每个数字与列表中的其他每个数字进行比较。O(n^2(.第二个函数应该是线性 O(n(。

from misc.decorator_timer import my_timer

def main():
"""
Finds the minimum number in a list
findMin1:  O(n^2)
findMin2:  O(n)
"""
findMin1(list(range(10**6)))
findMin1(list(range(10**7)))
findMin2(list(range(10**6)))
findMin2(list(range(10**7)))

@my_timer
def findMin1(array):
"""Finds min number in a list in O(n^2) time"""
for i in range(len(array)):
min_val = array[i]
for num in array:
if num < min_val:
min_val = num
return min_val

@my_timer
def findMin2(array):
"""Finds min number in a list in O(n) time"""
min_val = array[0]
for num in array:
if num < min_val:
min_val = num
return min_val

if __name__ == '__main__':
main()

我用下面制作的计时器装饰器对其进行了测试：

# ./misc/decorator_timer.py
import time
from functools import wraps

def my_timer(func):
"""Adds how long it took to run"""
@wraps(func)
def wrapper(*args, **kwargs):
t0 = time.time()
result = func(*args, **kwargs)
timedelta = time.time() - t0
print(f'nfunction:t"{func.__name__}"nruntime:t {timedelta:.08} sec')
return result
return wrapper

这是我得到的结果：

function:   "findMin1" 
runtime:    0.03258419 sec
function:   "findMin1" 
runtime:    0.35547304 sec
function:   "findMin2" 
runtime:    0.035234928 sec
function:   "findMin2" 
runtime:    0.33552194 sec

显然线性更好，但为什么findMin1线性增长，而不是预期的二次增长？

Answer 1

return 语句位于外部 for 循环内部，因此您只执行一次外部循环，然后立即返回。因此，第一种方法具有复杂性 O(n(。

如果你return min_val一次去缩进，把它移到外面的for循环之外，你会得到二次复杂度。