这个算法的大O代价函数是什么？

您如何以大O符号来描述下面的内容？这个算法的大O代价函数是什么？

rotors = [1,2,3,4,5 ...] 
widgets = ['a', 'b', 'c', 'd', 'e' ...] 

assert len(rotors) == len(widgets) 

for r in rotors: 
    for w in widgets: 
     ... 

    del widgets[0]

来源

2010-05-05 ʞɔıu

你是指del w [0]还是del widgets [0]？也就是说，你是否删除了转子中每个r的第一个小部件，或者每个小部件的第一个项目（在这种情况下，缩进是错误的？）或者是什么？ – Francesco 2010-05-05 17:37:24

这是O（n^2）。你可以看到，内部循环执行的次数为：

n + (n - 1) + (n - 2) + ... + 1

，因为一个小部件被删除每一个外循环迭代。那是（n^2 + n）/ 2，它是O（n^2）。

来源

2010-05-05 14:47:17

因为你正在经历两个循环它是O（n^2）。

来源

2010-05-05 14:41:12

这是一个过于简单的论点。但在这种情况下确实是正确的。 – polygenelubricants 2010-05-05 14:50:26

好吧，我不明白为什么事情复杂:)）它不是像他给了我们一个完整的算法... – 2010-05-05 15:32:49

该算法将具有的O的最坏情况性能（N^2）。

来源

2010-05-05 14:42:14

这种说法是错误的一般。你可以有嵌套循环，它是'O（N）'，它也可以是'O（2^N）'。它确实取决于算法本身，而不仅仅是结构嵌套。 – polygenelubricants 2010-05-05 14:53:35

耶，你说得对。没有想到一个人通过。更新:) – 2010-05-05 15:45:42

其实，给出最初的断言，最好的情况是O（n^2）。如果内循环比O（1）做得更多，那肯定不是最坏的情况。 – andand 2010-05-05 17:38:03

因为断言：

assert len(rotors) == len(widgets)

的O的答案（N ）是正确的，但在列表不一定相同的长度，一般情况下，你会叫它O（m * n个）。

来源

2010-05-05 14:46:53

+1对于假设len（转子）的重要性== len（小工具） – 2010-05-08 17:58:46

这是为O（n^2），但我觉得人失踪这一问题的部分删除。

The first loop you have n widgets. 
The second loop you have n-1 widgets. 
... 
The n-1 loop you have 2 widgets. 
The n loop you have 1 widgets.

你可能会认为你降低大O，但全部删除并以1/2乘以系数。

这是因为N +（N-1）+ ... + 2 + 1 = N（N + 1）/ 2。随着N趋于无穷大，它变成成n^2月2日这仅仅是为O（n^2）

来源

2010-05-05 14:48:00

在被两个相反和迂腐的风险，你真的没有提供足够的信息来笼统地回答这个问题条款。当然，表现并不比O（n^2）更好，但是由于你没有给出关于你在内部循环中做什么的细节，它通常会更糟。但是，假设内部循环发生的是O（1），那么整体性能为O（n^2）。

来源

2010-05-05 17:32:09 andand

我完全同意。 – redtuna 2010-05-07 17:35:10

是啊，这就是为什么这些大O问题总是很难搞清楚。但是如果我不得不猜测我会说O（n^2），因为你每次都要经过2次循环来执行一些操作。

来源

2010-05-07 11:56:17 daveangel

这个算法的大O代价函数是什么？

回答

相关问题