python - 时间复杂度最小数组数量

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 循环之外，您将获得二次复杂度。