时间和空间复杂性 - 用于内部循环的循环
时间是什么时候＆amp;以下代码的复杂性？
function SortFunction (entries):
sorted_entries = {}
while entries is not empty:
smallest entry = entries [0]
foreach entry in entries:
if (entry <smallest_entry):
smallest entry = entry
sorted_entries.add(smallest _entry)
entries.remove(smallest entry)
return sorted_entries
我认为复杂性的时间可能是O（n^2），但是在互联网上对于类似情况有不同的答案，所以我感到困惑。 那空间复杂性呢？
关于此主题的一个额外的小问题：
function PrintCol():
colours = { "Red", "Green", "Blue", "Grey" }
foreach colour in colours:
print(colour)
由于只有一个循环，这里的时间复杂性是o（n），对吗？ 空间复杂性？
What is the time & complexity of the code below?
function SortFunction (entries):
sorted_entries = {}
while entries is not empty:
smallest entry = entries [0]
foreach entry in entries:
if (entry <smallest_entry):
smallest entry = entry
sorted_entries.add(smallest _entry)
entries.remove(smallest entry)
return sorted_entries
I thought the time complexisty could be O(n^2) but there are different answers on the internet for similar situations, so I was confused.
And what about the space complexity?
And an extra small question about this topic:
function PrintCol():
colours = { "Red", "Green", "Blue", "Grey" }
foreach colour in colours:
print(colour)
The time complexity here is O(n) since there is only one loop, right?
Space complexity?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
循环时有n迭代，每次迭代的成本为o（n）。这是假设在线性时间内运行的添加和删除方法。然后总成本为o（n^2）。
您的第二个程序将花费O（n）。
There are n iterations of the outer while loop, and the cost of each iteration is O(n). This is assuming that the add and remove methods each run in linear time. The total cost is then O(n^2).
Your second program would have cost O(n).