建站
咨詢
售后
建站咨詢
新聞中心
今天我們來看下算法復(fù)雜度和效率的問題，在判斷一個算法的效率時，操作數(shù)量中的常數(shù)項和其他次要項常常是可以忽略的，只需要關(guān)注最高階項就能得出結(jié)論。那么我們?nèi)绾斡梅柖ㄐ缘呐袛嗨惴ǖ男誓兀克惴ǖ膹?fù)雜度分為兩部分：1、時間復(fù)雜度，即算法運行后對時間需求量的定性描述；2、空間復(fù)雜度，即算法運行后對空間需求量的定性描述。
創(chuàng)新互聯(lián)公司專注于集美企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè),成都商城網(wǎng)站開發(fā)。集美網(wǎng)站建設(shè)公司,為集美等地區(qū)提供建站服務(wù)。全流程按需網(wǎng)站建設(shè)，專業(yè)設(shè)計，全程項目跟蹤，創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)數(shù)據(jù)結(jié)構(gòu)重點關(guān)注的是算法的效率問題，因此，我們后面會集中于討論算法的時間復(fù)雜度；但其使用的方法完全可以用于空間復(fù)雜度的判斷！我們經(jīng)常在進(jìn)行算法的時間復(fù)雜度用大O表示法來進(jìn)行分析。下來對此種方法進(jìn)行說明，算法效率嚴(yán)重依賴于操作（Operation）數(shù)量；操作數(shù)量的估算可以作為時間復(fù)雜度的估算；在判斷時首先關(guān)注操作數(shù)量的最高次項。如下：
下來我們來分析下常見的時間復(fù)雜度：
1、線性階時間復(fù)雜度：O(n)。如下：
2、對數(shù)階時間復(fù)雜度：O(logn)。如下
3、平方階時間復(fù)雜度：O(n2)。如下：
下來我們來看看常見的時間復(fù)雜度，如下圖所示
常見的時間復(fù)雜度的比較，如下
下面我們通過實例來進(jìn)行分析下，下面的函數(shù)程序復(fù)雜度是怎樣的
int?find(int?a[],?int?n,?int?v)
{
????int?ret?=?-1;
????
????for(int?i=0;?i<=n;?i++)
????{
????????if(?a[i]?==?v?)
????????{
????????????ret?=?i;
????????????break;
????????}
????}
????
????return?ret;
}我們?nèi)绻x的數(shù)組 a[5] = {1, 2, 3, 4, 5}； 如果是 int min = find(a, 5, 1)； 這種則是最好情況了，僅需執(zhí)行 1 次循環(huán)，此時便是 O(1)；如果是 int max = find(a, 5, 5)；此時便是最壞的情況了，需要全部執(zhí)行，此時便是 O(n)。那么此時算法的最好與最壞情況便體現(xiàn)出來了，當(dāng)算法在最乖情況下仍然能滿足需求時，可以推斷，算法的最好情況和平均情況都滿足需求。在以后沒有進(jìn)行特殊說明時，所分析算法的時間復(fù)雜度都是指最壞時間復(fù)雜度。
算法的空間復(fù)雜度（Space Complexity），其定義為 S(n) = S(f(n))。其中 n 為算法的問題規(guī)模，f(n) 為空間使用函數(shù)，與 n 相關(guān)。推倒時間復(fù)雜度的方法同樣適用于空間復(fù)雜度，例如，當(dāng)算法所需要的空間是常數(shù)時，其空間復(fù)雜度為 S(1)。我么來看看下面這個程序的空間復(fù)雜度為多少
long?sum1(int?n)
{
????long?ret?=?0;
????int*?array?=?new?int[n];
????
????for(int?i=0;?i我們看到第一行為 1，第三行的 ret 定義也為 1，指針數(shù)組 array 的定義其空間復(fù)雜度為 n，下面兩個進(jìn)行 for 循環(huán)的空間復(fù)雜度分別為 1。因此整個程序所需的單位內(nèi)存為： n + 4；即空間復(fù)雜度：S(n+4) = S(n)。那么時間跟空間之間是否存在某種聯(lián)系呢？在多數(shù)情況下，算法的時間復(fù)雜度更令人關(guān)注，因為現(xiàn)在的內(nèi)存都很大。如果有必要的話，可以通過增加額外空間降低時間復(fù)雜度；同理，也可以增加算法的耗時降低空間復(fù)雜度。下來我們來看個空間換時間的示例代碼，代碼的背景是在 1-1000 中的某些數(shù)字搜組成的數(shù)組中，設(shè)計一個算法類找出出現(xiàn)次數(shù)最多的數(shù)字。
#include?
using?namespace?std;
void?sreach(int?a[],?int?len)
{
????int?pi[1000]?=?{0};
????int?max?=?0;
????
????for(int?i=0;?i我們來看看打印結(jié)果
我們看到打印了 3 和 6，因為大數(shù) 6 和 3 都出現(xiàn)了 3 次。那么此次我們的程序?qū)崿F(xiàn)中函數(shù)的時間復(fù)雜度為 O(n)。那么問題來了，當(dāng)兩個算法的大 O 表示法相同時，是否意味著兩個算法的效率完全相同呢？肯定是不相同的！通過今天對算法的時間復(fù)雜度和效率的學(xué)習(xí)，總結(jié)如下：1、時間復(fù)雜度是算法運行時對于時間的需求量；2、大 O 表示法用于描述算法的時間復(fù)雜度，它只關(guān)注操作數(shù)量的最高次項；3、常見的時間復(fù)雜度為：線性階，平方階和對數(shù)階；4、一般而言，在工程中使用的算法其復(fù)雜度都不超過 O(n3)；5、算法分析與設(shè)計時，重點考慮最壞情況下的時間復(fù)雜度，大 O 表示法用于適用于算法的空間復(fù)雜度；6、空間換時間是工程開發(fā)中常用的策略。
標(biāo)題名稱：算法時間復(fù)雜度及效率（二）-創(chuàng)新互聯(lián)
本文來源：http://www.ef60e0e.cn/article/dhescg.html
