在这种情况下，时间复杂度是多少?

Question

for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
function();
//do something
}
}
function() {
for(int i = 0; i < k; k++) {
//do something
}
}

因此，在另一个 for 循环中有一个循环，然后在内部循环中，有一个函数调用再次以线性时间复杂度运行。在这种情况下，我是在查看 O(n^2( 或 O(n^3( 的时间复杂度吗？

Answer 1

它是O(n^2*k)的时间复杂度。因为，一旦你进入第二个循环，对于每个j，你必须做function()，这是另一个循环，然后对于每个j，你正在做另一个复杂for loopO(k)：

for(int i = 0; i < n; i++) {             -----O(n)
for(int j = i+1; j < n; j++) {     -----O(n)
function();                      -----O(k)
//do something
}
}

因为

function() {
for(int i = 0; i < k; k++) {       -----O(k)
//do something
}
}

由于它们是嵌套的并且因为它们都是线性的，因此您可以得到 O(n × n × k( = O(n^2*k(。感谢 Jacob Steinebronn 的规范。 查看此链接链接 链接 1， 链接 2 了解更多信息。