问算法的时间复杂度计算

EN

有几种表示算法运行时的方法。最常用的符号之一是Big - O表示法。维基百科链接：符号表示法

大O表示法用于根据算法的运行时间或空间需求随输入大小的增长对算法进行分类。

现在，虽然符号的数学定义可能令人望而生畏，但您可以将其视为输入大小的多项式函数，去掉所有常数和低次多项式。

对于ex:大O中的ax^2 + bx + c是O(x^2) (我们去掉了所有常数a,b and c和低次多项式bx)。

现在，让我们考虑一下您的例子。但是在这样做之前，让我们假设每个操作都需要一个恒定的时间c。

第一个例子：

输入是：colours = { "Red", "Green", "Blue", "Grey" }，在for循环中循环这些元素。由于输入大小为4，运行时为4 * c。它是常量运行时，常量运行时在Big-O中被写为O(1)

第二个例子：

内部for循环运行total_columns时间，它有两个操作

for x from 0 to total_columns:
  sum += values[y][x]
  n += 1

所以，这需要2c * total_columns时间。并且，外部for循环运行total_rows时间，从而导致total_rows * (2c * total_columns) = 2c * total_rows * total_columns的总时间。在Big-O中，它被写成O(total_rows * total_columns) (我们去掉了常量)

当您走出外部循环时，最初设置为n的0将变成total_rows * total_columns，这就是为什么他们提到的答案是O(n)。

时间复杂性的一个很好的定义是：

“它是一个算法为完成其任务而执行的与输入大小相关的操作数”。

如果我们认为下面的问题输入大小可以定义为X= total_rows*total_columns。那么，操作的数量是多少呢？它又是X，因为由于操作sum += values[y][x] (忽略简单性的n += 1增量操作)，会有X添加。然后，考虑一下从X到2*X的双数组大小。会有多少次行动？又是2*X。正如您所看到的，当我们增加输入大小时，操作数的增加是线性的，这使得时间复杂度O(N)。

function CalculateAverageFromTable(values, total_rows, total_columns):
 sum = 0
 n = 0
 for y from 0 to total_rows:
      for x from 0 to total_columns:
          sum += values[y][x]
          n += 1

 return sum / n

对于你的第一个问题，原因是颜色是一个集。在python中，{}定义了一个集合。无论输入大小如何，从无序集访问元素都是O(1)时间复杂度。要获得更多信息，您可以查看这里。