大O

Question

有人能幫我找到這兩個函數的大O：

int sum(int A[], int i, int n) { 
    if (n == 1) 
     return A[i]; 
    return sum(A, i, n/2) + sum(A, i + n/2, (n+1)/2); 
} 

和的「排序」功能：

void swap(int& a, int& b) { 
    int temp = a; 
    a = b; 
    b = temp; 
} 

void swapMin(int A[], const int& index) { 
    int indexMin = index; 
    for (int i = index-1; i >= 0; --i) 
     if (A[i] < A[indexMin]) 
      indexMin = i; 

    swap(A[index], A[indexMin]); 
} 

void sort(int A[], int n) { 
    for (int i = n-1; i >= 0; --i) 
     swapMin(A, i); 
} 

我相信第一是O（1），第二個是O（n），但我不確定這是否正確。

Answer 1

的第一個功能，你可以這樣做：

然後你就可以使用生成函數解決它。

對於第二個，你可以使用六西格瑪符號：