大o計演算法

Ⅰ 大O表示法演算法的執行時間

在評估演算法性能時，我們通常關注的是其執行時間，這是通過所有基本操作的執行時間和次數來計算的。基本操作，如基本運算、賦值、比較和交換，構成了演算法的核心步驟。例如，在排序中，比較和交換是基本操作；而在線性查找中，數據的比較是關鍵步驟。

然而，實際的執行時間會受到多種因素影響，如編程語言、編譯器和CPU。為了解決這種歧義，大O表示法（O-notation）引入了一個假設，即所有計算機對相同基本操作的執行時間是可比的。我們關注的是演算法在最壞情況下的基本操作次數，即當問題規模（例如處理的數據量）n增長時，這些操作的最大執行次數。

時間復雜度，或漸近時間復雜度，是對演算法執行時間隨著問題規模增長的長期行為的描述。它關注的是基本操作執行次數的增長率，用一個函數T(n)表示，其中n是問題規模。我們通過確定T(n)的函數形式，然後分析其數量級，即其增長的速度或規模。具有相同數量級的函數集合用O(f(n))表示，其中f(n)是基準函數。如果T(n)和f(n)在增長速度上相似，我們可以說T(n)屬於O(f(n))。

換句話說，大O表示法幫助我們理解，當數據量n增大時，演算法執行時間將以何種比例增加，這是衡量演算法效率的重要指標。

大O表示法：稱一個函數g(n)是O(f(n))，當且僅當存在常數c>0和n0>=1，對一切n>n0均有|g(n)|<=c|f(n)|成立，也稱函數g(n)以f(n)為界或者稱g(n)囿於f(n)。記作g(n)=O(f(n))。 定義：如果一個問題的規模是n，解這一問題的某一演算法所需要的時間為T(n)，它是n的某一函數。T(n)稱為這一演算法的「時間復雜度」。當輸入量n逐漸加大時，時間復雜度的極限情形稱為演算法的「漸近時間復雜度」。