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

Question

我正在处理 water-collection between towers problem ，并尝试计算我的解决方案的 bigO 以供练习。

有一次，我从用户输入的高度数组构建了一个二维的“塔”数组。此步骤使用嵌套的 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

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

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

一般来说，您可以根据您想要的任何数量来表达算法的运行时间。许多图算法的运行时间取决于节点数(通常表示为 n)和边数(通常表示为 m)，例如 Dijkstra 算法，可以使运行时间 O(m + n log n)使用斐波那契堆。一些算法的运行时间取决于输出的大小(例如，Aho-Corasick string matching algorithm 在时间 O(m + n + z) 中运行，其中 m 和 n 是输入字符串的长度，z 是输入字符串的数量火柴)。一些算法依赖于许多其他参数 - 例如，count-min sketch在 O(ε-1 log δ-1) 时间内执行更新，其中 ε 和 δ 是算法启动时指定的参数。