如果我的函数有两个嵌套的for循环，它是否以二次时间运行？

Question

我正在学习用大O符号分析算法。我通过Ranum&；米勒的Problem Solving with Algorithms in Python textbook。其中一项任务如下：

Write two Python functions to find the minimum number in a list. The first function should compare each number to every other number on the list. 𝑂(𝑛2). The second function should be linear 𝑂(𝑛).

没有指导或解决方案，所以我是盲目的。以下是我对二次函数和线性函数的解：

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
        for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number


def find_min_linear(a_list):
    return min(a_list)

我的逻辑是，有两个nester for循环在问题a_list上迭代，这将给我O（n^2）运行时间。而对于第二种解决方案，我只是调用内置函数min()，这样应该有线性时间？（虽然现在我认为这可能意味着它有固定的时间？）

我最初误读了作业中的“查找列表中的最大数”，因此我也为max_number.编写了这些函数。我遵循了与min_number.相同的逻辑。如上所述，我对二次和线性时间的理解和实现正确吗

def find_max_quadratic(a_list):
    max_number = None
    for a_number in a_list:
        for item in range(len(a_list)):
            if a_number > a_list[item]:
                max_number = a_number
    return max_number


def find_max_linear(a_list):
    return max(a_list)

Answer 1

您分析和计算算法复杂性的逻辑是正确的。然而，我怀疑你的老师可能不喜欢你写的代码

线性函数的问题

def find_min_linear(a_list):
    return min(a_list)

您被要求编写一个函数，返回列表的最小值，为此，您。。。使用python内置函数返回列表的最小值

这对于任何实际应用都是一个好主意，因为python内置函数可能比您自己编写的任何函数都要快；您可以相信它没有bug，而不是浪费时间检查您自己的代码是否有bug

但是你的老师可能更感兴趣的是你提出了一个求最小值的算法，而不是你知道已经有一个python内置函数可以做到这一点。min函数确实是线性的，但是这个函数的存在只是因为有人能够首先提出一个线性算法，并用它来实现这个函数 . 事实上，我觉得很令人不安的是，你的老师没有明确禁止你在这个作业中使用python内置的min和max。如果我是一名学生，我可能会提到内置函数存在并以线性时间执行，然后我会编写自己的函数而不使用现有函数

二次函数的问题

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
        for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number

从技术上讲，你的函数是有效的，它是二次函数。然而，内部for循环很麻烦。变量item从未使用过；它的唯一目的是确保循环有n个迭代（其中n是列表的长度）。循环体将始终执行完全相同的操作；if中的条件要么总是true，要么总是false；如果它是真的，那么min_number = a_number将一次又一次地将相同的值写入相同的变量

换句话说：在for循环中重复执行这个if语句毫无意义；只要执行一次

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
    #    for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number

Tadaaaaaa！只需少一行，算法仍能正确执行并返回列表的最小值

该算法现在是线性的，而不是二次的。你的老师要你做一个二次算法。您可能认为可以添加一个for循环，使您的算法具有二次性。这在技术上是正确的，但是下面的算法也可以工作：

def find_min_quadratic(a_list):
    min_number = find_min_linear(a_list)
    for item in range(len(a_list)**2):
        beebboop = 57
    return min_number

毫无疑问，这个函数是二次函数——我们明确地包含了一个运行n^2次迭代的循环。但是你的老师可能觉得你在取笑他们

此外，如果你仔细阅读，你的作业文本上会说“第一个函数应该将每个数字与列表中的其他数字进行比较。”。你的二次函数没有这样做

二次算法

您已经找到了一个线性算法（通过从二次函数中删除一行），所以现在您仍然需要找到一个二次函数。这有点违反直觉，就我个人而言，我非常不喜欢这个任务。编写算法通常遵循以下步骤：

1. 表达问题
2. 找到一个算法来解决这个问题
3. 分析算法的复杂性
4. 找到一种新的算法，以较低的复杂度解决问题

因此，按照这些思路进行的任务将非常有意义：

1. 编写一个函数来查找列表的最小值
2. 分析函数的复杂性
3. 如果你的函数不是线性的，那么写一个新函数来寻找线性时间内列表的最小值

如果你已经找到了线性函数，那么寻找一个效率较低的函数是很尴尬的，这导致你添加了一个for循环，它无缘无故地浪费了时间

我认为赋值的目的不是人为地制造一个效率较低的函数，而是尝试提出一个完全不同的算法，然后理解它并非所有的算法都同样有效

您的老师明确地说：“第一个函数应该将每个数字与列表中的其他数字进行比较。”。所以我们可以用它来编写一个新函数：

def find_min_quadratic(a_list):
    # ...
    for a in a_list:
        # ...
        for b in a_list:
            if a > b:
                # ...
        # ...

尝试填充空格，使其返回最小值。您可以添加其他变量，也可以添加其他if语句，但不能添加其他for循环。提示：如何确定元素a是否为最小值？由于for b in a_list循环，我们能否找到a是否是最小值