带有嵌套 for 循环的 while 循环是 O(n) 还是 O(n^2)？
Is a while loop with a nested for loop O(n) or O(n^2)?
我有 2 个代码块。一个只有一个 while 循环，第二个在 while 循环内有一个 for 循环。我的教授告诉我选项 1 的算法复杂度为 O(n)，选项 2 的算法复杂度为 O(n^2)，但无法解释为什么会这样，除了指向嵌套的 for 循环。我很困惑，因为对于任何给定的大小 N，两者都执行完全相同数量的计算，这似乎并不表示它们具有不同的算法复杂性。
我想知道：
a) 如果我的教授是正确的，他们怎么能吹嘘同样的计算却有不同的大Os。
b) 如果我的教授不正确并且它们的复杂度相同，是 O(n) 还是 O(n^2)？为什么？
我使用由“#”表示的内联注释来记录计算。要交付的包裹应该是 N。Self.trucks 是一个列表。 self.isWorkDayComplete 是一个布尔值，由是否所有包裹都已送达决定。
选项 1：
# initializes index for fake for loop
truck_index = 0
while(not self.workDayCompleted):
# checks if truck index has reached end of self.trucks list
if(truck_index != len(self.trucks)):
# does X amount of calculations required for delivery of truck's packages
while(not self.trucks[truck_index].isEmpty()):
trucks[truck_index].travel()
trucks[truck_index].deliverPackage()
if(hub.packagesExist()):
truck[truck_index].travelToHub()
truck[truck_index].loadPackages()
# increments index
truck_index += 1
else:
# resets index to 0 for next iteration set through truck list
truck_index = 0
# does X amount of calculations required for while loop condition
self.workDayCompleted = isWorkDayCompleted()
选项 2：
while(not self.workDayCompleted):
# initializes index (i)
# each iteration checks if truck index has reached end of self.trucks list
# increments index
for i in range(len(trucks)):
# does X amount of calculations required for Delivery of truck's packages
while(not self.trucks[i].isEmpty()):
trucks[i].travel()
trucks[i].deliverPackage()
if(hub.packagesExist()):
truck[i].travelToHub()
truck[i].loadPackages()
# does X amount of calculations required for while loop condition
self.workDayCompleted = isWorkDayCompleted()
非常感谢任何帮助，谢谢！
a) if my professor is correct, and how they can boast the same calculations but have different big Os.
执行相同数量“基本操作”的两种算法具有相同的时间复杂度，无论代码的结构如何。
b) if my professor is incorrect and they are the same complexity, is it O(n) or O(n^2)? Why?
首先你要定义：什么是“n”？ n是卡车的数量吗？接下来，每辆卡车的“基本操作”数量是相同还是有所不同？
例如：如果每辆货车作业次数为常数C，则总作业次数为C*n。那就是复杂度 class O(n).
这两段代码似乎确实有效地实现了相同的算法（即用每辆卡车运送一个包裹，然后检查工作日是否完成，重复直到工作日完成）。从这个角度来看，你的怀疑是对的。
问题就变成了：它们是O(n)还是O(n2)？正如您所描述的，这无法确定，因为我们不知道完成工作日的条件是什么。它与卡车完成的工作量有关吗？没有这些信息，我们就无法推断外循环何时退出。据我们所知，条件是每辆卡车必须运送 2n 个包裹，复杂度实际上是 O(n 2n).
因此，如果您的教授是对的，我唯一的猜测是两个选项之间 isWorkDayCompleted() 的实现存在差异。但是，除非有类似的情况，否则这两个选项应该具有相同的复杂性。
无论如何，当涉及到这样的问题时，确保你们都在谈论同样的事情总是很重要的：
n是什么意思（大概是卡车的数量）- 您在计算什么（大概是送货的数量，也可能是工作日完成的支票）
- 结束状态是什么（这对我来说是危险信号——完成的工作日需要更好地定义）
随后的编辑让我相信这两个选项都是 O(n)，因为它们最终对每个包裹执行一到两次“旅行”操作，具体取决于卡车的数量及其容量。鉴于此，我认为您的核心问题（那些不同的控制结构是否会导致不同的复杂性分析）的答案是否定的，他们不会。
内部结构似乎也不太可能以某种重要方式影响代码复杂性，因此我的建议是与您的教授重新聚在一起，看看他们是否可以扩展他们的想法。这很可能是他们的疏忽，或者他们试图就您正在使用的某些组件的实现方式提出更微妙的观点。
如果你得到了他们的解释，并且发生了一些更复杂的事情，但你仍然无法理解，那可能应该是一个单独的问题（也许与这个问题相关）。
我有 2 个代码块。一个只有一个 while 循环，第二个在 while 循环内有一个 for 循环。我的教授告诉我选项 1 的算法复杂度为 O(n)，选项 2 的算法复杂度为 O(n^2)，但无法解释为什么会这样，除了指向嵌套的 for 循环。我很困惑，因为对于任何给定的大小 N，两者都执行完全相同数量的计算，这似乎并不表示它们具有不同的算法复杂性。
我想知道：
a) 如果我的教授是正确的，他们怎么能吹嘘同样的计算却有不同的大Os。
b) 如果我的教授不正确并且它们的复杂度相同，是 O(n) 还是 O(n^2)？为什么？
我使用由“#”表示的内联注释来记录计算。要交付的包裹应该是 N。Self.trucks 是一个列表。 self.isWorkDayComplete 是一个布尔值，由是否所有包裹都已送达决定。
选项 1：
# initializes index for fake for loop
truck_index = 0
while(not self.workDayCompleted):
# checks if truck index has reached end of self.trucks list
if(truck_index != len(self.trucks)):
# does X amount of calculations required for delivery of truck's packages
while(not self.trucks[truck_index].isEmpty()):
trucks[truck_index].travel()
trucks[truck_index].deliverPackage()
if(hub.packagesExist()):
truck[truck_index].travelToHub()
truck[truck_index].loadPackages()
# increments index
truck_index += 1
else:
# resets index to 0 for next iteration set through truck list
truck_index = 0
# does X amount of calculations required for while loop condition
self.workDayCompleted = isWorkDayCompleted()
选项 2：
while(not self.workDayCompleted):
# initializes index (i)
# each iteration checks if truck index has reached end of self.trucks list
# increments index
for i in range(len(trucks)):
# does X amount of calculations required for Delivery of truck's packages
while(not self.trucks[i].isEmpty()):
trucks[i].travel()
trucks[i].deliverPackage()
if(hub.packagesExist()):
truck[i].travelToHub()
truck[i].loadPackages()
# does X amount of calculations required for while loop condition
self.workDayCompleted = isWorkDayCompleted()
非常感谢任何帮助，谢谢！
a) if my professor is correct, and how they can boast the same calculations but have different big Os.
执行相同数量“基本操作”的两种算法具有相同的时间复杂度，无论代码的结构如何。
b) if my professor is incorrect and they are the same complexity, is it O(n) or O(n^2)? Why?
首先你要定义：什么是“n”？ n是卡车的数量吗？接下来，每辆卡车的“基本操作”数量是相同还是有所不同？
例如：如果每辆货车作业次数为常数C，则总作业次数为C*n。那就是复杂度 class O(n).
这两段代码似乎确实有效地实现了相同的算法（即用每辆卡车运送一个包裹，然后检查工作日是否完成，重复直到工作日完成）。从这个角度来看，你的怀疑是对的。
问题就变成了：它们是O(n)还是O(n2)？正如您所描述的，这无法确定，因为我们不知道完成工作日的条件是什么。它与卡车完成的工作量有关吗？没有这些信息，我们就无法推断外循环何时退出。据我们所知，条件是每辆卡车必须运送 2n 个包裹，复杂度实际上是 O(n 2n).
因此，如果您的教授是对的，我唯一的猜测是两个选项之间 isWorkDayCompleted() 的实现存在差异。但是，除非有类似的情况，否则这两个选项应该具有相同的复杂性。
无论如何，当涉及到这样的问题时，确保你们都在谈论同样的事情总是很重要的：
n是什么意思（大概是卡车的数量）- 您在计算什么（大概是送货的数量，也可能是工作日完成的支票）
- 结束状态是什么（这对我来说是危险信号——完成的工作日需要更好地定义）
随后的编辑让我相信这两个选项都是 O(n)，因为它们最终对每个包裹执行一到两次“旅行”操作，具体取决于卡车的数量及其容量。鉴于此，我认为您的核心问题（那些不同的控制结构是否会导致不同的复杂性分析）的答案是否定的，他们不会。
内部结构似乎也不太可能以某种重要方式影响代码复杂性，因此我的建议是与您的教授重新聚在一起，看看他们是否可以扩展他们的想法。这很可能是他们的疏忽，或者他们试图就您正在使用的某些组件的实现方式提出更微妙的观点。
如果你得到了他们的解释，并且发生了一些更复杂的事情，但你仍然无法理解，那可能应该是一个单独的问题（也许与这个问题相关）。