回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p><strong>首先我研究了以下问题:</strong></p>
<p><a href="https://stackoverflow.com/questions/25796205/onm-time-complexity">O(N+M) time complexity</a><br/>
<a href="https://stackoverflow.com/questions/40366904/comparing-complexity-of-onm-and-omaxn-m">Comparing complexity of O(n+m) and O(max(n,m))</a><br/>
<a href="https://stackoverflow.com/questions/26569408/big-o-of-these-nested-loops">Big-O of These Nested Loops</a><br/>
<a href="https://stackoverflow.com/questions/19879739/is-this-function-onm-or-onm">Is this function O(N+M) or O(N*M)?</a><br/>
<a href="https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm">How to find time complexity of an algorithm</a></p>
<p><strong>然而,我仍然没有100%的信心。也就是说,我有以下python示例代码:</strong></p>
<pre><code>adjList = [[4,7,8,9],[7,7,5,6],[1,4,3],[2,9],[2,1,7]]
for i in adjList:
for j in i:
print "anything else"
</code></pre>
<p><strong>我开始认为这是一个O(n+m)算法,下面是我的推理:</strong></p>
<p>我有一个列表。为了举例说明,这里的整数是随机选取的。这实际上是一个邻接列表,其中顶点1链接到顶点4、7、8和9,依此类推。你知道吗</p>
<p>我知道<strong>adjList[I][j]</strong>将从第I个列表返回第j个项目。所以adjList[0][2]</strong>是<strong>8</strong></p>
<p></strong>的第一个<strong>将在每个<strong>i</strong>列表中循环。如果我们有<strong>N</strong>列表,这是一个<strong>O(N)</strong>。你知道吗</p>
<p>用于</strong>的第二个<strong>将遍历列表中的每个<strong>j</strong>元素。但在这种情况下,j不是固定值,例如,第一个列表有4个元素(4,7,8,9),第三个列表有3个元素(1,4,3)。因此,在第二个for结束时,将循环<strong>M</strong>次,M是每个不同j值的总和。所以,<strong>M</strong>是每个列表元素的总和。因此<strong>O(M)</strong></p>
<p>在本例中,</strong>的<strong>第一个应该循环<strong>5次,而<strong>第二个应该循环<strong>16次。总共有21个循环。如果我将adjList更改为如下列表中的单个大列表:</p>
<pre><code>adjList = [[4,7,8,9,7,7,5,6,1,4,3,2,9,2,1,7]]
</code></pre>
<p>它仍然会循环通过<strong>第二个<strong>中的<strong>16个<strong>元素,再加上<strong>第一个<strong>的<strong>时间。你知道吗</p>
<p>因此,我可以说算法将循环<strong>N</strong>次加<strong>M</strong>次。其中,<strong>N</strong>是adjList中的列表数,<strong>M</strong>是adjList中每个列表中元素的总和。所以<strong>O(N+M)</strong></p>
<p><strong>那么,我的怀疑在哪里?</strong><br/>
我在任何地方都发现嵌套循环的例子是<strong>O(N^2)</strong>或<strong>O(N*M)</strong>。即使人们提到他们可以是其他的东西,而不是那些我没有发现的例子。我还没有找到O(N+m)嵌套循环的例子。所以我仍然怀疑我的推理是否正确。你知道吗</p>
<p>我怀疑这是否不是一个O(N*M)算法。但我不会详细说明。<br/>
因此,我的最后一个问题仍然是:这个推理是否正确,所说的算法是否真的是O(N+M)?如果不是,你能告诉我我的错误在哪里吗?你知道吗</p>