解释时间复杂性？
如何在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时间复杂度中寻找的是指令执行的大致次数。 因此，在第一个函数中，您有可执行语句：
intMatrix[i][j] = 0;
由于可执行语句每次都花费相同的时间，因此它是O（1）。 因此，对于第一个函数，您可以将其剪切为如下所示并从可执行语句返回：
i: execute n times{//Time complexity=n*(n+1)/2 j: execute i times{ intMatrix[i][j] = 0; //Time complexity=1 } }
回过头来，i循环执行n次，j循环执行i次。 例如，如果n = 5，则执行的指令数将是5 + 4 + 3 + 2 + 1 = 15。 这是一个算术系列，可以用n（n + 1）/ 2表示。 因此，函数的时间复杂度为n（n + 1）/ 2 = n ^ 2/2 + n / 2 = O（n ^ 2） 。
对于第二个function，您正在寻找类似的东西。 您的可执行语句是：
dividend[j] = dividend[j] / divisor[i];
现在，有了这个陈述，它有点复杂，正如你可以从维基百科看到的那样，教科书长划分的复杂性是O（n ^ 2）。 但是，除数和除数不要使用你的变量n，因此它们不依赖于它。 我们称之为被除数和除数，也就是矩阵“m”的实际内容。 因此可执行语句的时间复杂度为O（m ^ 2）。 继续简化第二个function：
i: execute n times{ //Time complexity=n*(n*(1*m^2))=O(n^2*m^2) j: execute n times{ //Time complexity=n*(1*m^2) if statement: execute ONCE{ //Time complexity=1*m^2 dividend[j] = dividend[j] / divisor[i]; //Time complexity=m^2 } } }
向后工作，您可以看到内部语句将采用O（m ^ 2），并且由于if语句每次都花费相同的时间，因此其时间复杂度为O（1）。 你的最终答案是O（n ^ 2平方公尺）。 由于除法在现代处理器上花费的时间很少，因此通常估计为O（1）（为了更好地解释为什么会这样做，请参阅此内容），教授可能正在为第二个函数寻找O（n ^ 2）。
两者都是O（N 2 ） 。 在最坏的情况下，您正在处理N 2项。
第二个例子在最好的情况下可能只是O（N） （如果第二个参数全为零）。
我不确定你是如何得到其他多项式的。 通常，确切的复杂性并不重要（即使用更高级别的语言时）。
Big O表示法或时间复杂度，描述了数据大小（n）的变化与给定算法处理它所需的时间/空间大小之间的关系。
在你的情况下，你有两个循环。 对于每个n个数（外循环），您处理n个项（在内循环中）项。 因此，你有O（n 2 ）或“二次”时间复杂度。
因此，对于少量的n，差异可以忽略不计，但是对于更大数量的n，它很快就会停止。
如算法2中那样从除数中消除0不会显着改变时间复杂度，因为检查数字= 0是否为O（1）并且几个数量级小于O（n 2 ）。 在该特定情况下消除内环仍然是O（n），并且仍然与执行O（n 2 ）所花费的时间相比相形见绌。 你的第二个算法，因此在技术上成为（最好的情况）O（n）（如果除数系列中只有零）。