解釋時間複雜性？

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）（如果在除數系列中只有零）。