如何導出執行時間增長率（Big O）？

Question

所以我有下面的代碼，我需要得到執行時間增長率，但我不知道從哪裏開始。我的問題是，我該如何去做這件事？任何幫助，將不勝感激。

謝謝。

// function to merge two sorted arrays 
int merge (int smax, char sArray[], int tmax, char tArray[], char target[]) 
{ 
    int m, s, t; 
    for (m = s = t = 0; s < smax && t < tmax; m++)  
    { 
     if (sArray[s] <= tArray[t]) 
     { 
      target[m] = sArray[s]; 
      s++; 
     } 
     else 
     { 
      target[m] = tArray[t]; 
      t++; 
     } 
    } 
    int compCount = m; 
    for (; s < smax; m++) 
    { 
     target[m] = sArray[s++]; 
    } 
    for (; t < tmax; m++) 
    { 
     target[m] = tArray[t++]; 
    } 
    return compCount; 
} 

Answer 1

其實很簡單。

看，第一個for循環在每次迭代中增加s或t，所以它是O(smax + tmax)。第二個循環顯然是O(smax)，第三個是O(tmax)。總共我們得到O(smax + tmax)。

（存在一些聰明的方法來證明，但我故意留出來。）

Answer 2

所有圈由（SMAX + t最大）的迭代次數的限制。所以你可以說算法是O(max(smax,tmax))或O(smax +tmax)。