解释时间复杂性？

Question

我们如何找到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吗？再次，如果没有，请问有人可以解释为什么？

Answer 1

在大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循环执行我的时间。例如，如果n = 5，则执行的指令数将是5 + 4 + 3 + 2 + 1 = 15。这是一个算术级数，可以用n（n + 1）/ 2表示。函数的时间复杂度因此是n（n + 1）/ 2 = n^2/2 + n/2 = O（n^2）。

对于第二个函数，您正在寻找类似的东西。你的可执行语句是：

dividend[j] = dividend[j]/divisor[i]; 

现在，这种说法这是一个有点复杂，因为你可以从wikipedia看，教科书长除法的复杂度为O（n^2）。然而，红利和除数不会使用你的变量n，所以他们不依赖于它。我们称分红和除数，即矩阵“m”的实际内容。所以可执行语句的时间复杂度是O（m^2）。继续前进，以简化第二功能：

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（平方公尺），由于if语句花费的时间是相同的每一次，它的时间复杂性是O（1）。你的最终答案是O（n^2m^2）。由于分区在现代处理器上花费的时间很少，通常估计为O（1）（请参阅this以更好地解释为什么会出现这种情况），您的教授可能会在第二个函数中寻找O（n^2）。

Answer 2

两者都是O（N ）。您正在处理N项目在最坏的情况下。

第二个例子可能只是O（N）在最好的情况下（如果第二个参数全为零）。

我不知道如何得到其他多项式。通常确切的复杂性并不重要（即使用高级语言时）。

Answer 3

大O符号或时间复杂度描述了数据大小（n）的变化与给定算法处理它所需的时间/空间大小之间的关系。

在你的情况下，你有两个循环。对于n（外部循环）的每个数字，您处理n个项目（在内部循环中）项目。因此在你有O（n ）或“二次”时间复杂度。

因此，对于少数n的差异可以忽略不计，但对于更大数量的n，它很快就会停下来。

如算法2中那样从除数中消除0并不会显着改变时间复杂度，因为检查数字= 0是否为O（1）并且比O少几个数量级（n）。在特定情况下消除内部循环仍然是O（n），并且仍然是O（n ）所花费的时间。你的第二个算法，因此在技术上成为（最好的情况）O（n）（如果在除数系列中只有零）。