算法簡介

任何問題的解決都有一定的方法和步驟，算法就是計算機(jī)解決問題過程的描述。從程序設(shè)計的角度看，算法由一系列求解問題的指令構(gòu)成，能根據(jù)規(guī)范的輸入，在有限的時間內(nèi)獲得有效的輸出結(jié)果，代表了用系統(tǒng)的方法來描述解決問題的一種策略機(jī)制。

算法復(fù)雜度這一指標(biāo)用于考量算法需要的時間和空間。算法的時間復(fù)雜度，即程序執(zhí)行時間增長的變化趨勢?？臻g復(fù)雜度是指一個程序在運(yùn)行過程中臨時占用存儲空間大小的一個量度。

一般來說，常見的時間復(fù)雜度量級有常數(shù)階、對數(shù)階、線性階、線性對數(shù)階、平方階、指數(shù)階、階乘階等，依次按照順序時間復(fù)雜度越來越大，執(zhí)行效率也越來越低。

選擇適合算法

算法優(yōu)化是指通過對算法進(jìn)行更好的設(shè)計以提升程序的性能，程序中的算法優(yōu)化可以從選擇合適的算法以及算法自身的優(yōu)化這兩方面進(jìn)行考慮，本節(jié)結(jié)合常用的排序算法進(jìn)行說明。

常用的排序算法有十余種，分為基于比較的插入、選擇、交換這三類，如冒泡排序、快速排序等。下面選擇三類排序算法中的幾個典型算法及優(yōu)化思路進(jìn)行介紹，分析每種算法的復(fù)雜度及其性能的差異，闡述不同應(yīng)用場景下選擇合適算法對程序性能的影響：

冒泡排序

冒泡排序是一種簡單的交換排序算法。通過元素的兩兩比較，判斷是否符合排序要求，如果不符合就交換位置來達(dá)到排序的目的。對于n個需要排序的數(shù)據(jù)來說，其算法復(fù)雜度為。其每次排序之后仍會繼續(xù)進(jìn)行下一輪的比較，無效計算較多，因此只適用于數(shù)據(jù)量較小的場景。

直接插入排序

插入排序是通過把序列中的值插入一個有序序列對應(yīng)的位置上，直到該序列結(jié)束。插入排序的賦值操作次數(shù)是比較操作次數(shù)減去(n-1)次，平均來說插入排序算法復(fù)雜度為，但在部分?jǐn)?shù)據(jù)有序的情況下其效率比冒泡排序更快。

簡單選擇排序

這種排序方式每次從待處理數(shù)據(jù)中選出最小的，放在已經(jīng)排好序的序列末尾，直至所有排序結(jié)束。假設(shè)有n個待排序的數(shù)據(jù)，則比較的總次數(shù)為n*(n-1)/2，時間復(fù)雜度為。可以看出選擇排序的對比次數(shù)較多但數(shù)據(jù)移動次數(shù)較少，在數(shù)據(jù)量大的情況下其效率明顯優(yōu)于冒泡排序，適用于大多數(shù)排序場景。

改進(jìn)算法策略

通過前文的描述已經(jīng)說明了算法的性能表現(xiàn)會對程序性能產(chǎn)生較大影響，所以在保證正確性的前提下通過改進(jìn)算法策略提升程序性能是十分有必要的。改進(jìn)算法策略的方法歸結(jié)起來可以分為以下兩點：

1. 從算法過程出發(fā)，盡量減少算法復(fù)雜度，提高其運(yùn)行的效率。

2. 從算法編碼出發(fā)，運(yùn)用一些技巧優(yōu)化算法中的編碼方式，從編碼角度提升算法性能。

枚舉算法

假設(shè)輸入向量包含下面7個元素，分別為(8，-33，16，9，-12，45，67)，則該向量的連續(xù)子向量的最大和為x[3-7]的總和125，此算法實現(xiàn)及改進(jìn)思路如下：

枚舉算法實現(xiàn)。此向量中所有子向量數(shù)都是正數(shù)時，顯然子向量最大和就是整個輸入向量的和。當(dāng)輸入向量中含有負(fù)數(shù)時，遍歷所有數(shù)組下標(biāo)范圍[i,j]的子向量求和，通過比較計算出最大和。

枚舉算法優(yōu)化

上述枚舉算法示例中存在部分重復(fù)運(yùn)算，此時可以利用一個變量保存之前的運(yùn)算結(jié)果避免部分冗余計算。經(jīng)過改進(jìn)后算法的復(fù)雜度為，改進(jìn)后部分代碼如下：

分治算法

可以采用分治技術(shù)將問題分解成2個與原問題形式相同的子問題分別遞歸求解。把向量序列從中間分為左右A和B兩部分，把A作為新的輸入序列求出左半部分的最大子向量和A1，同理求出右半部分的最大子向量和B1，將跨越左右部分的最大向量和稱為C1。最后取這三個子向量和中的最大值即可。該算法的時間復(fù)雜度為，整體性能高于前兩種算法。

線性算法

此問題還可以從頭到尾掃描數(shù)組的思路求解。假設(shè)往一個長度為i的向量后面插入第i+1個數(shù)，此時只需要從包含第i+1個數(shù)和不包含第i+1個數(shù)的序列中選出最大的子向量和，而后者是已知的。因此x[i]作為末尾元素時能找到的最大子向量和和要么是x[i]本身，要么是x[i-1]作為末尾元素時能找到的最大子向量和再拼接上x[i]。該代碼時間復(fù)雜度為。