如果我的函数有两个嵌套的 for 循环，它会在二次时间内 运行 吗？
If my function has two nested for loops does it run in quadratic time?
我正在学习使用大 O 表示法分析算法。我正在研究 Ranum & Miller 的 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)
我的逻辑是有两个嵌套 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)
你的逻辑是对的，你分析自己实现的方法应该是怎么做的。
第二个可能令人困惑，在那种情况下，您正在调用某个函数，该函数已在语言库本身中实现。这也有其自身的复杂性，在本例中为 O(n).
如果你想制作你自己的线性复杂度的方法，那么你可以这样实现它：
- 定义最小变量
- 遍历数组并将循环中的值与定义的最小值进行比较
- 如果 min > 循环值则将其重新分配给 min
你分析和计算算法复杂度的逻辑是正确的。但是，我怀疑您的老师可能不喜欢您编写的代码。
你的线性函数有问题
def find_min_linear(a_list):
return min(a_list)
你被要求写一个 return 列表最小值的函数，为了做到这一点，你...使用 python 内置函数 returns列表的最小值。
这对于任何实际应用来说都是一个好主意，因为 python 内置函数可能比您自己编写的任何函数都快；并且您可以相信它没有错误，而不是浪费时间检查您自己的代码是否存在错误。
但是你的老师可能对你想出一个找到最小值的算法更感兴趣，而不是你知道已经有一个 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 中的条件要么永远为真，要么永远为假；如果为真，那么 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
太棒了！只需少一行，算法仍然可以正确执行，return 列表的最小值。
算法现在是线性的，而不是二次的。你的老师问你一个二次算法。您可能认为可以添加一个 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 次迭代的循环。但是你的老师可能会觉得你在取笑他们。
此外，如果你仔细阅读，你的作业文本会说“第一个函数应该将每个数字与列表中的每个其他数字进行比较。”。你的二次函数没有这样做。
二次算法
您已经找到了一个线性算法（通过从二次函数中删除一条线），所以现在您仍然需要找到一个二次函数。这有点违反直觉，就我个人而言，我非常不喜欢这个任务。编写算法通常遵循以下步骤：
- 表达一个问题
- 找到解决问题的算法
- 分析算法的复杂度
- 找到一个新的算法来解决复杂度较低的问题
因此，按照这些思路进行作业很有意义：
- 编写一个函数来查找列表的最小值
- 分析函数的复杂性
- 如果您的函数不是线性的，则编写一个新函数以在线性时间内找到列表的最小值。
如果您已经找到了线性函数，那么寻找一个效率较低的函数会很尴尬，这导致您添加了一个 for 循环，无缘无故地浪费时间。
我认为作业的重点不是人为地做一个效率较低的函数，而是尝试想出一个完全不同的算法，然后理解并不是所有的算法都同样高效。
你的老师明确地说“第一个函数应该将每个数字与列表中的每个其他数字进行比较。”。所以我们可以用它来编写一个新函数：
def find_min_quadratic(a_list):
# ...
for a in a_list:
# ...
for b in a_list:
if a > b:
# ...
# ...
尝试填空，使 return 成为最小值。您可以添加其他变量，可以添加其他 if 语句，但不要添加其他 for 循环。提示：如何判断一个元素a是否为最小值？由于 for b in a_list 循环，我们能否找到 a 是否是最小值？
二次解如下：
def findMinQuad(aList):
overallmin = alist[0]
for i in aList:
issmallest = True
for j in a List:
if i > j:
issmallest = False
if issmallest:
overallmin = i
return overallmin
由于我们使用嵌套的 for 循环对输入 aList 进行两次迭代，我们知道答案是二次时间 O(n^2)。嵌套循环还确保我们将每个数字与列表中的每个其他数字进行比较。
线性解如下：
def findMinLin(aList):
minsofar = aList[0]
for i in aList:
if i < minsofar:
minsofar = i
return minsofar
这个很容易解释，我们只是假设第一个数字是最小的，然后我们遍历列表以查看是否找到更小的数字。如果我们这样做，那么该数字就是新的最小数字，到循环结束时，无论保存为最小数字的是什么，实际上都是最小数字。
我正在学习使用大 O 表示法分析算法。我正在研究 Ranum & Miller 的 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)
我的逻辑是有两个嵌套 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)
你的逻辑是对的，你分析自己实现的方法应该是怎么做的。
第二个可能令人困惑，在那种情况下，您正在调用某个函数，该函数已在语言库本身中实现。这也有其自身的复杂性，在本例中为 O(n).
如果你想制作你自己的线性复杂度的方法，那么你可以这样实现它：
- 定义最小变量
- 遍历数组并将循环中的值与定义的最小值进行比较
- 如果 min > 循环值则将其重新分配给 min
你分析和计算算法复杂度的逻辑是正确的。但是，我怀疑您的老师可能不喜欢您编写的代码。
你的线性函数有问题
def find_min_linear(a_list):
return min(a_list)
你被要求写一个 return 列表最小值的函数，为了做到这一点，你...使用 python 内置函数 returns列表的最小值。
这对于任何实际应用来说都是一个好主意，因为 python 内置函数可能比您自己编写的任何函数都快；并且您可以相信它没有错误，而不是浪费时间检查您自己的代码是否存在错误。
但是你的老师可能对你想出一个找到最小值的算法更感兴趣，而不是你知道已经有一个 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 中的条件要么永远为真，要么永远为假；如果为真，那么 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
太棒了！只需少一行，算法仍然可以正确执行，return 列表的最小值。
算法现在是线性的，而不是二次的。你的老师问你一个二次算法。您可能认为可以添加一个 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 次迭代的循环。但是你的老师可能会觉得你在取笑他们。
此外，如果你仔细阅读，你的作业文本会说“第一个函数应该将每个数字与列表中的每个其他数字进行比较。”。你的二次函数没有这样做。
二次算法
您已经找到了一个线性算法（通过从二次函数中删除一条线），所以现在您仍然需要找到一个二次函数。这有点违反直觉，就我个人而言，我非常不喜欢这个任务。编写算法通常遵循以下步骤：
- 表达一个问题
- 找到解决问题的算法
- 分析算法的复杂度
- 找到一个新的算法来解决复杂度较低的问题
因此，按照这些思路进行作业很有意义：
- 编写一个函数来查找列表的最小值
- 分析函数的复杂性
- 如果您的函数不是线性的，则编写一个新函数以在线性时间内找到列表的最小值。
如果您已经找到了线性函数，那么寻找一个效率较低的函数会很尴尬，这导致您添加了一个 for 循环，无缘无故地浪费时间。
我认为作业的重点不是人为地做一个效率较低的函数，而是尝试想出一个完全不同的算法，然后理解并不是所有的算法都同样高效。
你的老师明确地说“第一个函数应该将每个数字与列表中的每个其他数字进行比较。”。所以我们可以用它来编写一个新函数：
def find_min_quadratic(a_list):
# ...
for a in a_list:
# ...
for b in a_list:
if a > b:
# ...
# ...
尝试填空，使 return 成为最小值。您可以添加其他变量，可以添加其他 if 语句，但不要添加其他 for 循环。提示：如何判断一个元素a是否为最小值？由于 for b in a_list 循环，我们能否找到 a 是否是最小值？
二次解如下：
def findMinQuad(aList):
overallmin = alist[0]
for i in aList:
issmallest = True
for j in a List:
if i > j:
issmallest = False
if issmallest:
overallmin = i
return overallmin
由于我们使用嵌套的 for 循环对输入 aList 进行两次迭代，我们知道答案是二次时间 O(n^2)。嵌套循环还确保我们将每个数字与列表中的每个其他数字进行比较。
线性解如下：
def findMinLin(aList):
minsofar = aList[0]
for i in aList:
if i < minsofar:
minsofar = i
return minsofar
这个很容易解释，我们只是假设第一个数字是最小的，然后我们遍历列表以查看是否找到更小的数字。如果我们这样做，那么该数字就是新的最小数字，到循环结束时，无论保存为最小数字的是什么，实际上都是最小数字。