说明

这是一份关于增长阶的学习指南，包含过往讲座、作业和讲义的链接，以及额外的练习题，帮助你学习这些概念。

作业

重要提示： 如需查看已发布的作业答案，请访问主网站。

• 实验 9

讲座

• 效率

阅读材料

• Section 2.8

增长阶

算法的增长阶是对计算机程序随输入规模增大所需运行时间的近似描述。增长阶忽略了固定操作所需的常数因子，而关注与输入规模成比例增长的操作。例如，具有线性增长阶的程序在输入翻倍时通常需要两倍的运行时间。

增长阶通常使用 Big-Theta 或 Big-O 记法来描述， 但这些记法超出了本课程的范围。

下表总结了最常见的增长阶：

常数时间

当算法具有常数增长阶时，意味着无论输入规模增大多少，它总是需要固定数量的步骤。

例如，考虑访问列表的第一个元素：

first_post = posts[0]

即使列表增长到一百万个元素，该操作也始终只需要一步。

我们可以用表格来可视化这种关系：

我们还可以用图表来可视化：

常数运行时间是最理想的，但对于需要处理多条数据的算法来说通常是不可能的。

对数时间

当算法具有对数增长阶时，它的增长与输入规模的对数成正比。

二分搜索算法就是一个以对数时间运行的算法示例。

以下是伪代码：

def search_list(nums, target_num):
    """ Returns the index of TARGET_NUM in sorted list NUMS or -1 if not found.
    >>> search_list([1, 2, 3, 4], 3)
    2
    >>> search_list([14, 23, 37, 48, 59], 23)
    1
    >>> search_list([14, 23, 37, 48, 59], 47)
    -1
    """
    min_index = 1
    max_index = len(nums)
    while min_index <= max_index:
        middle_index = (min_index + max_index) // 2
        if target_num == nums[middle_index]:
            return middle_index
        elif target_num > nums[middle_index]:
            min_index = middle_index + 1
        else:
            max_index = middle_index - 1
    return -1

该算法使用循环来查看列表中的多个元素，但关键在于，它不会查看列表中的每个元素。具体来说，它查看 lg2(n) 个元素，其中 n 是列表中的元素数量。

我们可以用表格来可视化这种关系：

我们也可以用图表来看：

随着输入规模的增加，步数确实在增加，但增长速度非常慢。

线性时间

当算法具有线性增长阶时，其步数与输入规模成正比增加。

名副其实的线性搜索算法就是以线性时间运行的。

代码显示了它相比二分搜索的简洁性：

def search_list(nums, target_num):
    """ Returns the index of TARGET_NUM in an unsorted list NUMS or -1 if not found.
    >>> search_list([3, 2, 1, 4], 3)
    2
    >>> search_list([14, 59, 99, 23, 37, 22], 23)
    3
    >>> search_list([14, 59, 99, 23, 37, 22], 47)
    -1
    """
    index = 1
    while index < len(nums):
        if nums[index] == target_num:
            return index
        index += 1
    return -1

这一次，循环会查看列表中的每个元素。这种穷举搜索对于在无序列表中搜索元素是必要的，因为无法缩小特定元素可能所在的范围。该算法始终需要至少与列表中元素数量相同的步数。

我们可以用表格形式来看：

或用图表：

二次时间

当算法具有二次增长阶时，其步数与输入规模的平方成正比增加。

几种列表排序算法以二次时间运行，如选择排序。该算法从列表前端开始，然后不断在列表中找到下一个最小值，并将其与当前值交换。

以下是选择排序的伪代码：

def linear_sort(nums):
    """Performs an in-place sorting of NUMS.
    >>> l = [2, 3, 1, 4]
    >>> linear_sort(l)
    >>> l
    [1, 2, 3, 4]
    """
    i = 0
    while i < len(nums):
        min_index = i
        j = i + 1
        # Find next smallest value
        while j < len(nums):
            if nums[j] < nums[min_index]:
                min_index = j
            j += 1
        # Swap if new minimum found
        if min_index != i:
            nums[i], nums[min_index] = nums[min_index], nums[i]
        i += 1

关于该算法需要注意的重要点是是嵌套循环：它遍历列表中的每个元素，并对每个元素再次遍历剩余的元素。在这种情况下，该算法最终会查看 1/2 * (n^2 - n) 个值，其中 n 是列表中的元素数量。

下表显示了它对于不同大小的列表会检查多少个元素：

以下是图表形式：

表格和图表都表明，该算法的步数增长速度比之前的算法快得多。

指数时间

当算法具有超多项式增长阶时，其步数的增长速度比输入规模的多项式函数更快。

当算法必须查看值的每种排列时，通常需要超多项式时间。例如，考虑一个生成给定密码长度的所有可能数字密码的算法。

对于密码长度为 2 的情况，它会生成 100 个密码：

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

该算法至少需要 10^2 步，因为每个数字（0-9）有 10 种可能，它必须尝试 2 个数字中每个数字的所有可能性。

对于任意给定的密码长度 n，该算法需要 10^n 步。该运行时间的增长速度惊人，因为每增加一个数字就需要 10 倍的步数。

下表显示了仅前 5 位数字的增长速度：

以下是图表形式：

综合对比

现在我们已经看了算法可能运行时间的示例，让我们在图表上比较它们：

该图表更清楚地表明，这些运行时间之间存在明显差异，尤其是随着输入规模的增加。由于现代计算机程序越来越多地处理大型数据集（如来自数百万用户或传感器的数据），运行时间效率非常重要。

练习题

Q1：Is Prime

is_prime 关于 n 的增长阶是什么？

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

选择其中一个：

• 常数
• 对数
• 线性
• 二次
• 指数
• 以上都不是

Q2：Growth: Bar

bar 关于 n 的增长阶是什么？

def bar(n):
    i, sum = 1, 0
    while i <= n:
        sum += biz(n)
        i += 1
    return sum

def biz(n):
    i, sum = 1, 0
    while i <= n:
        sum += i**3
        i += 1
    return sum

选择其中一个：

• 常数
• 对数
• 线性
• 二次
• 指数
• 以上都不是

def foo(lst, i):
    mid = len(lst) // 2
    if mid == 0:
        return lst
    elif i > 0:
        return foo(lst[mid:], -1)
    else:
        return foo(lst[:mid], 1)

def bonk(n):
    sum = 0
    while n >= 2:
        sum += n
        n = n / 2
    return sum