Computer Science · College · College and University

演算法:複雜度與常見模式

大 O 表示法、常見的排序與搜尋演算法,以及技術面試和課程中常考的遞迴模式。

38 cards · basic cards · AI-written, checked twice. Edit anything.

Opens in your browser, no account. Get the iPhone and iPad app · Android app

大 O 表示法衡量的是什麼?

Show answer

當輸入規模增加時,演算法所需的執行時間或空間如何成長。

請定義 O(1) 時間複雜度。

Show answer

常數時間,不論輸入規模多大,執行時間都不會改變。

請定義 O(n) 時間複雜度。

Show answer

線性時間,執行時間與輸入規模 n 成正比。

請定義 O(log n) 時間複雜度。

Show answer

對數時間,執行時間隨輸入規模的對數成長。

請定義 O(n^2) 時間複雜度。

Show answer

平方時間,執行時間隨輸入規模的平方成長。

請定義 O(n log n) 時間複雜度。

Show answer

線性對數時間,執行時間為 n 乘以 n 的對數。

請定義 O(2^n) 時間複雜度。

Show answer

指數時間,輸入規模每增加一,執行時間就變成兩倍。

以索引存取陣列元素的時間複雜度是多少?

Show answer

O(1) 常數時間。

在未排序的陣列中搜尋某個值,時間複雜度是多少?

Show answer

O(n) 線性時間。

對已排序的陣列做二元搜尋,時間複雜度是多少?

Show answer

O(log n) 對數時間。

使用二元搜尋之前,陣列必須滿足什麼條件?

Show answer

陣列必須是已排序的。

在陣列開頭插入一個元素,時間複雜度是多少?

Show answer

O(n) 線性時間。

在容量足夠的動態陣列尾端新增一個元素,時間複雜度是多少?

Show answer

O(1) 均攤常數時間。

在雜湊表中搜尋的平均時間複雜度是多少?

Show answer

雜湊函數良好時為 O(1) 常數時間。

快速排序在平均情況下的時間複雜度是多少?

Show answer

O(n log n) 線性對數時間。

23 more cards in the app