peterhpchen
10/19/2017 - 11:54 AM

Pre-Test Question 2

Pre-Test Question 2

答案是: O(n)

以下面邏輯計算複雜度:

int[] alphabetIndex = new int[26];  //1

foreach (char alphabet in array1)   //n
{
    int index = alphabet - 'A';
    alphabetIndex[index]++;
}

foreach (char alphabet in array2)   //n
{
    int index = alphabet - 'A';
    if (alphabetIndex[index] <= 0) return false;
}

return true;                        //1

總計為2n + 2, 當n無窮大時, n的係數2及+2可以忽略不計, 故答案為O(n)