<p>N和M的定义如下:</p>
<blockquote>
<p>Thereby I can say that the algorithm will loop N times plus M times. Where N is the number of lists in adjList and M is the sum of elements in each one of the lists inside adjList. So O(N+M)</p>
</blockquote>
<p>根据这个定义,算法是O(M)<sup>1</sup>。为了理解N为什么消失,你需要考虑N和M之间的关系。假设你有两个列表,你想看看这两个列表中每一个可能的项对。我们将保持简单:</p>
<pre><code>list1 = [1, 2, 3]
list2 = [4, 5]
</code></pre>
<p>所以你想看看这六对:</p>
<pre><code>pairs = [(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5)]
</code></pre>
<p>总共是3*2=6。现在概括一下,假设list1有N个项目,list2有M个项目。对的总数是N*M,所以这将是一个O(N*M)算法。你知道吗</p>
<p>现在假设您不需要查看每一对,而只需要查看一个或另一个列表中的每一项。现在您只需查看两个列表串联中出现的所有值:</p>
<pre><code>items = [1, 2, 3, 4, 5]
</code></pre>
<p>总共是3+2=5项。现在推广一下,得到N+M,这是一个O(N+M)算法。你知道吗</p>
<p>鉴于此,如果你的情况确实是O(N+M),我们应该期望你的情况和上面的情况是相同的。换言之,我们应该期望您的案例涉及到查看两个不同列表中的所有项目。但你看:</p>
<pre><code>all_lists = [[4,7,8,9],[7,7,5,6],[1,4,3],[2,9],[2,1,7]]
</code></pre>
<p>这和:</p>
<pre><code>list1 = [4,7,8,9]
list2 = [7,7,5,6]
list3 = [1,4,3]
list4 = [2,9]
list5 = [2,1,7]
</code></pre>
<p>而在O(N+M)情况下,只有两个列表,这里有五个列表!所以这不能是O(N+M)。你知道吗</p>
<p>然而,这应该给你一个如何更好地描述的想法。(提示:除了M和N之外,还可能包括J、K和L。)</p>
<p>你的错误的根源是,在前两个例子中,M和N被定义为彼此分开,但你对M和N的定义是重叠的。为了使M和N有意义地相加或相乘,它们必须彼此无关。但在你的定义中,M和N的值是相互关联的,所以在某种意义上,它们重复了不应该重复的值。你知道吗</p>
<p>或者,换一种方式来说,假设所有内部列表的长度之和加起来等于M。如果必须对每个值采取两个步骤而不是一个步骤,那么结果仍然是常数C乘以M。对于任何常数C,C*O(M)仍然是O(M)。所以在外循环中所做的功已经被O(M)项计算了(直到一个常数乘数)。你知道吗</p>
<p><sub>备注:</sub></p>
<p><sub>1。好吧,不完全是,正如<a href="https://stackoverflow.com/questions/43837443/is-it-correct-to-say-that-this-algorithm-is-onm/43837579#comment74711684_43837552">Stefan Pochmann</a>指出的。由于技术上的原因,用O(max(N,
M) )因为如果任何内部列表为空,您仍然需要访问它们。</sub></p>