大O符號

習題預習

1. 假設有一個有序數組，對於一個特定數字進行查找的時間複雜度是多少？
2. 給定一個n乘以n矩陣，計算其行列式的時間複雜度是多少？
3. 給定一個長度為n的數組，在其中查找最小和最大值的時間複雜度是多少？
4. 給定一個字符串和一個字符，查找該字符在字符串中出現的次數的時間複雜度是多少？
5. 給定一個n乘以n矩陣和一個矩陣，計算其矩陣乘法的時間複雜度是多少？

說明知識

Big O Notation是用來描述算法時間複雜度的一種方式，它告訴我們當輸入規模n變大時，算法執行時間增長的情況。通常以O(f(n))表示，其中f(n)是輸入規模n的函數，表示算法執行時間的成長率。

例如O(1)表示輸入規模n沒有影響算法執行時間，常見的例子是取陣列中的某個元素。O(n)表示當輸入規模n增大時，算法執行時間線性增長，常見例子有遍歷陣列或搜尋未排序的陣列。O(n^2)表示當輸入規模n增加時，算法執行時間呈平方級數增長，常見例子是選擇排序或冒泡排序。還有一些更高階的算法，如O(log n)表示當輸入規模增加時，算法執行時間呈對數級數增長，通常用在二分查找等算法中。

總之，Big O Notation是一種用數學方式表達算法時間複雜度的方式，能夠幫助我們評估算法的效率並選擇最優解決方案。

彙總重點

1. Big O Notation是一種用於評估算法效率的工具，其主要關注點是算法的最壞情況下的執行時間和空間複雜度。

2. Big O Notation的計算方式是忽略常數和低階項，只保留最高次的項，並用O( )來表示。

3. O(1)表示算法的執行時間或空間複雜度是一個固定值，即不會隨著輸入規模變化而變化。

4. O(log n)表示算法的執行時間或空間複雜度是隨著輸入規模的增加以對數方式增加的。

5. O(n)表示算法的執行時間或空間複雜度是隨著輸入規模的增加以線性方式增加的。

6. O(n²)表示算法的執行時間或空間複雜度是隨著輸入規模的增加以平方方式增加的。

7. O(2ⁿ)表示算法的執行時間或空間複雜度是隨著輸入規模的增加以指數方式增加的，往往是一種非常低效的算法。

8. 在評估算法效率時，我們希望找到一個更高效的算法，使其複雜度為O(log n)或O(n)等較低的級別。

9. 對於複雜度相同的算法，我們需要進一步分析它們的常數項和低階項，以找到最優解法。

知識測驗

1. 給定一個包含n個元素的整數數組，找出其中出現次數超過n/2次的元素。求該算法的時間複雜度。

答案：O(n)

2. 給定一個包含n個元素的整數數組，找出其中出現次數最多的前k個元素。求該算法的時間複雜度。

答案：O(nlogk)

3. 將一個包含n個元素的整數數組按升序排序。求該算法的時間複雜度。

答案：O(nlogn)

4. 給定一個長度為n的字符串，找出其中出現次數最多的k個字串。求該算法的時間複雜度。

答案：O(n^2logk)

5. 在一個無向圖中，找出長度為k的簡單環路。求該算法的時間複雜度。

答案：O(n^k * poly(n))