gpt4 book ai didi

java - 解释一下时间复杂度?

转载 作者:行者123 更新时间:2023-12-01 18:37:21 24 4
gpt4 key购买 nike

如何找到以 N 和 Big-O 表示的给定算法的时间复杂度?例如,

    //One iteration of the parameter - n is the basic variable
void setUpperTriangular (int intMatrix[0,…,n-1][0,…,n-1]) {
for (int i=1; i<n; i++) { //Time Complexity {1 + (n+1) + n} = {2n + 2}
for (int j=0; j<i; j++) { //Time Complexity {1 + (n+1) + n} = {2n + 2}
intMatrix[i][j] = 0; //Time complexity {n}
}
} //Combining both, it would be {2n + 2} * {2n + 2} = 4n^2 + 4n + 4 TC
} //O(n^2)

时间复杂度是 O(n^2) 和 4n^2 + 4n + 4 吗?如果没有,您是如何得到答案的?

另外,我有一个关于时间复杂度的两参数矩阵的问题。

//Two iterations in the parameter, n^2 is the basic variable
void division (double dividend [0,…,n-1], double divisor [0,…,n-1])
{
for (int i=0; i<n; i++) { //TC {1 + (n^2 + 1) + n^2} = {2n^2 + 2}
if (divisor[i] != 0) { //TC n^2
for (int j=0; j<n; j++) { //TC {1 + (n^2 + 1) + n^2} = {2n^2 + 2}
dividend[j] = dividend[j] / divisor[i]; //TC n^2
}
}
} //Combining all, it would be {2n^2 + 2} + n^2(2n^2 + 2) = 2n^3 + 4n^2 + 2 TC
} //O(n^3)

这个是 O(N^3) 和 2n^3 + 4n^2 + 2 吗?再说一遍,如果不是,有人可以解释一下原因吗?

最佳答案

两者都是O(N2)。在最坏的情况下,您正在处理 N2 个项目。

在最好的情况下(如果第二个参数全为零),第二个示例可能只是O(N)

我不确定你是如何得到其他多项式的。通常,确切的复杂性并不重要(即使用高级语言时)。

关于java - 解释一下时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21384598/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com