一，如何衡量一個算法的好壞

答：看時間效率和空間效率

二，算法效率

• 算法效率分析分為兩種： 第一種是時間效率，第二種是空間效率。
• 時間效率  被稱為  時間復(fù)雜度，而  空間效率  被稱作  空間復(fù)雜度。
• 時間復(fù)雜度主要衡量的是一個    算法的運行速度，
• 空間復(fù)雜度主要衡量的是一個    算法所需要的額外空間

三，時間復(fù)雜度

1，時間復(fù)雜度的概念

時間復(fù)雜度的定義：在計算機科學(xué)中，算法的時間復(fù)雜度是一個數(shù)學(xué)函數(shù)，它定量描述了該算法的運行時間。

一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？

是可以都上機測試，但是這很麻煩，所以才有了時間復(fù)雜度這個分析方式。

一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù)雜度。

2，大O的漸進表示法

Func1 執(zhí)行的基本操作次數(shù) ：

實際中我們計算時間復(fù)雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。

大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學(xué)符號

3，推導(dǎo)大O階方法

1、用常數(shù)1取代 運行時間 中的所有 加法常數(shù) 。

2、在 修改后的 運行次數(shù)函數(shù)中，只保留 最高階項 。

3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)(系數(shù))。得到的結(jié)果就是大O階。

使用大O的漸進表示法以后，F(xiàn)unc1的時間復(fù)雜度為：

通過上面我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結(jié)果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。

平時所說的時間復(fù)雜度或空間復(fù)雜度，都是指在 最壞情況下的 時間復(fù)雜度

那么平均時間復(fù)雜度怎么算，我這里給個例子，大家了解一下就行

4，常見時間復(fù)雜度計算舉例

求復(fù)雜度 一定要結(jié)合 算法的思想

• 例1    O(N)

• 例2    O(M+N)

• 例3    O(100)  寫作100即可

• 例4     O(1/2*n^2 - 1/2*n) -> O(n^2)[最壞情況每次都要交換，即逆序]

最好情況是執(zhí)行一輪 O(N)

• 例5    0()    最好情況就是在中間的時候，一次直接找到，就是1

這是二分查找，最壞情況就是最后一次才找到

第一次:  n/2^1 第二次:  n/2^2  ....  .....  第x次:  n/2^x = 1 (最后要找的那個數(shù)據(jù)看作1)

對第x次進行等式變形:n = 2^x -> x =

• 例6      O(N)

遞歸的時間復(fù)雜度 = 遞歸的次數(shù) * 每次遞歸執(zhí)行的次數(shù)

這個題目 每次遞歸執(zhí)行的次數(shù)是 1 ，因為 三目運算符 無論結(jié)果如何實際上只運行一次

所以 時間復(fù)雜度為 O(N-1) - > O(N)

• 例7    O(2^N)

先了解一下 什么是 斐波那契數(shù)列

實際上，通過其遞歸公式我們可以得出這樣的一個式子

2^0 + 2^1 + 2^2 + ... ... + 2^(N-2) + 2^ (N-1) = S(n)

下圖是主播簡單的推導(dǎo)

這是一個等比數(shù)列

再等比數(shù)列求和= S(n) = 2^n - 1

則 時間復(fù)雜度為 O(2^N)

5，以后常遇到的復(fù)雜度

O(1)    <   O(logN)[默認(rèn)以2為底]    <  O(N)    <    O(N*logN)    <   O(N^2)

四，空間復(fù)雜度

空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 。

空間復(fù)雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復(fù)雜度算的是變量的個數(shù)。

空間復(fù)雜度計算規(guī)則基本跟時間復(fù)雜度類似，也使用大O漸進表示法。

計算舉例：

冒泡排序的空間復(fù)雜度是O(1)

斐波那契數(shù)列動態(tài)開辟了N個空間，空間復(fù)雜度是O(N)

遞歸調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)個空間?？臻g復(fù)雜度為O(N)

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論