一，如何衡量一個(gè)算法的好壞

答：看時(shí)間效率和空間效率

二，算法效率

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

三，時(shí)間復(fù)雜度

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

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

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

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

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

2，大O的漸進(jìn)表示法

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

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

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

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

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

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

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

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

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

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

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

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

求復(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()    最好情況就是在中間的時(shí)候，一次直接找到，就是1

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

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

對(duì)第x次進(jìn)行等式變形:n = 2^x -> x =

• 例6      O(N)

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

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

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

• 例7    O(2^N)

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

實(shí)際上，通過其遞歸公式我們可以得出這樣的一個(gè)式子

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

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

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

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

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

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

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

四，空間復(fù)雜度

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度 。

空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。

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

計(jì)算舉例：

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

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

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

總結(jié)

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

最新評(píng)論