这个算法是O（n+m）对吗？

Question

首先我研究了以下问题：

O(N+M) time complexity
Comparing complexity of O(n+m) and O(max(n,m))
Big-O of These Nested Loops
Is this function O(N+M) or O(N*M)?
How to find time complexity of an algorithm

然而，我仍然没有100%的信心。也就是说，我有以下python示例代码：

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"

我开始认为这是一个O（n+m）算法，下面是我的推理：

我有一个列表。为了举例说明，这里的整数是随机选取的。这实际上是一个邻接列表，其中顶点1链接到顶点4、7、8和9，依此类推。你知道吗

我知道adjList[I][j]将从第I个列表返回第j个项目。所以adjList[0][2]是8

的第一个将在每个i列表中循环。如果我们有N列表，这是一个O（N）。你知道吗

用于的第二个将遍历列表中的每个j元素。但在这种情况下，j不是固定值，例如，第一个列表有4个元素（4,7,8,9），第三个列表有3个元素（1,4,3）。因此，在第二个for结束时，将循环M次，M是每个不同j值的总和。所以，M是每个列表元素的总和。因此O（M）

在本例中，的第一个应该循环5次，而第二个应该循环16次。总共有21个循环。如果我将adjList更改为如下列表中的单个大列表：

adjList = [[4,7,8,9,7,7,5,6,1,4,3,2,9,2,1,7]]

它仍然会循环通过第二个中的16个元素，再加上第一个的时间。你知道吗

因此，我可以说算法将循环N次加M次。其中，N是adjList中的列表数，M是adjList中每个列表中元素的总和。所以O（N+M）

那么，我的怀疑在哪里？
我在任何地方都发现嵌套循环的例子是O（N^2）或O（N*M）。即使人们提到他们可以是其他的东西，而不是那些我没有发现的例子。我还没有找到O（N+m）嵌套循环的例子。所以我仍然怀疑我的推理是否正确。你知道吗

我怀疑这是否不是一个O（N*M）算法。但我不会详细说明。
因此，我的最后一个问题仍然是：这个推理是否正确，所说的算法是否真的是O（N+M）？如果不是，你能告诉我我的错误在哪里吗？你知道吗

Answer 1

N和M的定义如下：

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)

根据这个定义，算法是O（M）¹。为了理解N为什么消失，你需要考虑N和M之间的关系。假设你有两个列表，你想看看这两个列表中每一个可能的项对。我们将保持简单：

list1 = [1, 2, 3]
list2 = [4, 5]

所以你想看看这六对：

pairs = [(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5)]

总共是3*2=6。现在概括一下，假设list1有N个项目，list2有M个项目。对的总数是N*M，所以这将是一个O（N*M）算法。你知道吗

现在假设您不需要查看每一对，而只需要查看一个或另一个列表中的每一项。现在您只需查看两个列表串联中出现的所有值：

items = [1, 2, 3, 4, 5]

总共是3+2=5项。现在推广一下，得到N+M，这是一个O（N+M）算法。你知道吗

鉴于此，如果你的情况确实是O（N+M），我们应该期望你的情况和上面的情况是相同的。换言之，我们应该期望您的案例涉及到查看两个不同列表中的所有项目。但你看：

all_lists = [[4,7,8,9],[7,7,5,6],[1,4,3],[2,9],[2,1,7]]

这和：

list1 = [4,7,8,9]
list2 = [7,7,5,6]
list3 = [1,4,3]
list4 = [2,9]
list5 = [2,1,7]

而在O（N+M）情况下，只有两个列表，这里有五个列表！所以这不能是O（N+M）。你知道吗

然而，这应该给你一个如何更好地描述的想法。（提示：除了M和N之外，还可能包括J、K和L。）

你的错误的根源是，在前两个例子中，M和N被定义为彼此分开，但你对M和N的定义是重叠的。为了使M和N有意义地相加或相乘，它们必须彼此无关。但在你的定义中，M和N的值是相互关联的，所以在某种意义上，它们重复了不应该重复的值。你知道吗

或者，换一种方式来说，假设所有内部列表的长度之和加起来等于M。如果必须对每个值采取两个步骤而不是一个步骤，那么结果仍然是常数C乘以M。对于任何常数C，C*O（M）仍然是O（M）。所以在外循环中所做的功已经被O（M）项计算了（直到一个常数乘数）。你知道吗

_备注：

_{1。好吧，不完全是，正如Stefan Pochmann指出的。由于技术上的原因，用O（max（N， M） ）因为如果任何内部列表为空，您仍然需要访问它们。}

Answer 2

你最大的错误是你没有清楚地指出M和N是什么意思。你知道吗

例如：

• 访问nxm矩阵中的所有单元是O(N*M)。你知道吗
• 如果你把这个矩阵展平成一个有P个单元格的列表，那么访问就是O(P)。你知道吗
• 然而P == N*M在这种情况下。。。所以O(M*N)和O(P)的意思是一样的。。。在这种情况下。你知道吗

看看你的推理，你似乎已经把M和p的模拟值混为一谈了（我说模拟值是因为矩形阵列和不规则阵列是不一样的）

So, M is the sum of elements of every list.

这不是我使用M的方式。更重要的是，这不是您所看到的其他各种引用使用M的方式。特别是那些讨论nxm矩阵或nxmavge（M）参差不齐数组的。这就是你的困惑。你知道吗

请注意，M和N不是自变量/参数。如果你用N来衡量一个问题，那就隐含地改变了M的值

提示：在对复杂性进行推理时，一种确保你得到正确答案的方法是回到最基本的方面。算出计算所执行操作的公式，并说明它们的原因，而不是试图说明“大O”符号是如何组成的。你知道吗

Answer 3

如果代码如下所示：

for i in adjList:
    <something significant 1>   
    for j in i:
        <something significant 2>

那我同意你的看法。但是<something significant 1>缺少（python执行循环的内部工作不值得考虑），因此没有理由包含O(N)部分。大O符号不是用来计算每一件事情的，它是用来显示当输入变大时算法是如何伸缩的。所以我们来看看什么是重要的，这意味着你的代码应该被认为是O(M)。你知道吗

嵌套循环通常被认为是O(N*M)的原因是，通常N被定义为外循环的迭代次数（正如您所做的），而M被定义为每个外循环的内循环迭代次数，而不是总的。因此，公共定义中的N*M等于定义中的M。你知道吗

编辑：有些人认为应该考虑循环时间，例如考虑大量空列表的情况。正如下面的代码所示，仅仅构造这样一个嵌套列表要比嵌套循环花费更长的时间。对于一个小的构造，通常会更复杂。因此，我不认为这是值得考虑的时间循环。你知道吗

from time import time

start = time()

L = [[] for _ in range(10000000)]

construction_time = time() - start
start = time()

for sub in L:
    for i in sub:
        pass

loop_time = time() - start

print(construction_time / loop_time)  # typically between 3 and 4