这种算法的时间复杂度(Big-O)是多少
for (int i = 1; i < n; i++) {
for (int j = 1; j < i; j++) {
for (int k = 1; k < j; k++) {
x++;
}
}
}
是指数级的吗?
假设输入为 n
谢谢!
for (int i = 1; i < n; i++) { // O(n) time complexity
for (int j = 1; j < i; j++) { // O(n) time complexity
for (int k = 1; k < j; k++) { // O(n) time complexity
x++;
}
}
}
第一个循环执行n
计算次数。你的第二个循环继续,直到i
达到它的状态,即n
,k
继续,直到j
达到它的条件。每个循环都达到相同的条件, n
因此,每个循环的时间复杂度为 O(n)
;因为它们是嵌套的,所以将每个 n 相乘,这导致总时间复杂度为 O(n^3)
每个循环都是O(n)
的,因此整体是O(n^3)
它将是 0(n^3) 复杂度,因为有 3 个复杂度为 0(n) 的循环。随着循环次数的增加,方法的时间复杂度会不断增加。所以你的程序中有 n 个循环,那么程序的时间复杂度将为 0(n^n)。您可以参考此 http://www.programmerinterview.com/index.php/data-structures/big-o-notation/以获取更多参考。