使用二维值计算 bigO 运行时，其中一维长度未知

Question

我正在研究 water-collection between towers problem，并试图计算我的练习解决方案的 bigO。

有一次，我根据用户输入的身高数组构建了一个 'towers' 的二维数组。此步骤使用嵌套 for 循环，其中内部循环运行 height 多次。

我的 BigO 适合这一步吗 n * maxHeight？

我从未见过任何类型的 BigO 使用这样的变量，但话又说回来，我还是个新手，所以这可能是一个经验问题。

我不认为高度问题可以作为一个常数被注销，因为没有理由塔的高度不会定期超过塔的数量。

  //convert towerArray into 2D array representing towers
var multiTowerArray = [];
for (i = 0; i < towerArray.length; i++) {
  //towerArray is the user-input array of tower heights
    multiTowerArray.push([]);
    for (j = 0; j < towerArray[i]; j++) {
        multiTowerArray[i].push(1);
    }
}

Answer 1

对于初学者来说，根据数量给予一段代码的大 O 运行时间是完全合理的 - 而且并不少见输入中元素的数量以及输入中元素的 size。例如，counting sort 运行s 时间 O(n + U)，其中 n 是输入数组中元素的数量，U 是数组中的最大值。所以是的，你绝对可以说你的代码的运行时间是 O(nU)，其中 n 是元素的数量，U 是数组中任意位置的最大值。

另一种选择是说代码的运行时间是 O(n + S)，其中 S 是数组中所有元素的总和，因为内部循环运行s 等于数组元素的总和。

一般来说，您可以根据需要的任何数量来表达算法的运行时间。许多图算法都有一个运行时间，它取决于节点数（通常表示为n）和边数（通常表示为m），例如Dijkstra的算法，可以在运行使用 Fibonacci 堆的时间 O(m + n log n)。一些算法有一个运行时间取决于输出的大小（例如，Aho-Corasick string matching algorithm runs in time O(m + n + z), where m and n are the lengths of the input strings and z is the number of matches). Some algorithms depend on a number of other parameters - as an example, the count-min sketch 在时间 O(ε^-1 log δ^-1),其中ε和δ为算法开始时指定的参数。

使用二维值计算 bigO 运行时，其中一维长度未知

Calculating bigO runtime with 2D values, where one dimension has unknown length

big-o