成人app

理解復雜度概念

點擊打開在線編譯器,邊學邊練


1. 時間空間復雜度定義

1) 時間復雜度

時間復雜度表示一個程序運行所需要的時間,其具體需要在機器環境中才能得到具體的值,但我們一般并不需要得到詳細的值,只是需要比較快慢的區別即可,為此,我們需要引入時間頻度(語句頻度)的概念。

時間頻度中,n稱為問題的規模,當n不斷變化時,時間頻度T(n)也會不斷變化。一般情況下,算法中的基本操作重復次數的是問題規模n的某個函數,用T(n)表示,若有某個輔助函數f(n),使得當n趨近于無窮大時,T(n)/f(n)的極限值為不等于零的常數,則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間復雜度,簡稱時間復雜度。

2)空間復雜度

成人app一個程序的空間復雜度是指運行完一個程序所需內存的大小,其包括兩個部分。

a)固定部分。這部分空間的大小與輸入/輸出的數據的個數多少、數值無關。主要包括指令空間(即代碼空間)、數據空間(常量、簡單變量)等所占的空間。這部分屬于靜態空間。

b)可變空間,這部分空間的主要包括動態分配的空間,以及遞歸棧所需的空間等。這部分的空間大小與算法有關。

 

2. 度量時間復雜度的兩種方法

1)事后統計法

顧名思義,就是指在程序運行結束之后直接查看運行時間的方式進行時間復雜度的統計,通常采用利用計算機的計時器對不同算法編制的程序進行運行時間的比較,從而確認一個算法的效率。

成人app但這種方法有很多缺陷:

成人appa)特別依賴計算機環境,同一套算法可能在不同的計算機上面有著截然不同的效果,老式的計算機和現代電腦的算力完完全全不是一個級別的處理速度。

b)算法的測試困難,有時一套算法需要海量的數據才能真正比較出效果,而為了設計這樣的海量數據以及正確性,則需要花費大量的時間,而對于不同的數據,同一算法又有不一樣的效果,故對于數據的使用很難去抉擇。

成人app也正是因為有這樣的缺陷,

2)事先估計法

與事后統計法不一樣,事先統計法采取在計算機編譯程序前對該算法進行預估的方式估算。我們可以通過利用時間頻度以及函數的思維進行對時間復雜度的解析。

3)函數符號:

〇表示最壞情況,Ω表示最好情況,θ表示平均情況,我們常用的分析使用O進行表示即可。對于一個算法的時間復雜度而言,n表示其執行問題的規模,O(n)表示執行該問題需要的時間量級,如O(n)表示線性級別,O(n2)表示平方級別,其中n主要的判斷方式為算法中循環結構的執行次數。

成人app以下為一些常用的基本公式:

a)O(a)=O(1)      其中a為常數

b)O(an)=O(n)     其中a為常數

c)O(an2++bn+c)=O(n2成人app)      其中a,b,c均為常數,結果只與最大項n有關



本文固定URL:http://hnsaiyang.com/course/91

第一章 數據結構入門
第二章 鏈表
第三章 棧
第四章 隊列
第五章 從C語言到C++
第六章 串,數組,矩陣,廣義表
第七章 樹
第八章 圖
第九章 算法—查找
第十章 算法—排序
第十一章 算法&競賽,思維培養
第十二章 后記
Dotcpp在線編譯      (登錄可減少運行等待時間)