❶ 什麼是線性時間演算法
計算公式：K（N）=AO（N）+B
線性時間
在計算復雜性理論，一個被稱為線性時間或 Ο（n）時間的演算法，表示此演算法解題所需時間正比於輸入資料的大小，通常以n表示。換句話說，執行時間與輸入資料大小為線性比例。例如將一列數字加總的所需時間，正比於串列的長度。
❷ 【比較難寫的演算法】最壞情況線性時間的選擇
實際上比平均情況下線性時間的選擇要復雜很多（演算法導論上偽代碼都沒有）
問題是快速排序要求樞紐元在最後一個，如果採用hoare的劃分演算法，就沒有這個要求。而給出的是樞紐元的值，然後要找到位置（搜索一遍），再交換。
如果採用hoare劃分法，不用搜索，不過演算法和書上描述的就稍有不同了。
另外，因為代碼復雜，所以對於隨機輸入，此演算法較慢
下面是hoare劃分的選擇代碼
# include <ctime>
# include <cstdlib>
# include <iostream>
inline void swap(int &x, int&y)
{
int temp = x;
x = y;
y = temp;
}
// A[p..r]
int hoarePartitionX(int *A, int p, int r, int x)
{
int i = p - 1;
int j = r + 1;
for(;;)
{
while( A[--j] > x)
;
while( A[++i] < x)
;
if(i<j)
{
swap(A[i], A[j]);
}
else
{
return j;
}
}
}
// A[0..size-1]
void insertionSort(int *A, int size)
{
int i;
int key;
for(int j=1; j<size; j+=1)
{
key = A[j];
i = j - 1;
while(i >= 0 && A[i] > key)
{
A[i+1] = A[i];
i -= 1;
}
A[i+1] = key;
}
}
// return the ith smallest element of A[p..r]
int select(int *A, int p, int r, int i)
{
if(p == r) // only one element, just return
{
return A[p];
}
// #1. groupNum & rest
int groupNum = (r - p + 1) / 5; // not counting the rest
int rest = (r - p + 1) % 5;
// #2. sort the groups
for(int t=0; t<groupNum; t+=1)
{
insertionSort(A + p + t*5, 5);
}
if(rest != 0)
{
insertionSort(A + p + groupNum * 5, rest);
}
// #3. get the mid value x
int *mids;
if(rest == 0)
mids = new int[groupNum];
else
mids = new int[groupNum+1];
for(int t=0; t<groupNum; t+=1)
{
mids[t] = A[ p + t*5 + 2 ];
}
if(rest != 0)
{
mids[groupNum] = A[ p + groupNum*5 + (rest-1)/2 ];
}
int x;
if( rest == 0 )
{
x = select(mids, 0, groupNum-1, (groupNum-1) / 2 + 1);
}
else
{
x = select(mids, 0, groupNum, groupNum / 2 + 1);
}
delete []mids;
// #4. partition with x
int k = hoarePartitionX(A, p, r, x) - p + 1; // so the value A[p+k-1] is the kth smallest
// #5.
if(i <= k)
{
return select(A, p, p+k-1, i);
}
else
{
return select(A, p+k, r, i-k);
}
}
int main()
{
int array[100];
for(int i=0; i<100; i+=1)
array[i] = i;
for(int i=0; i<100; i+=1)
{
int rnd = rand()%100;
swap(array[0], array[rnd]);
}
std::cout << select(array, 0, 99, 82);
std::cin.get();
return 0;
}
❸ 關於 世紀 和年代的演算法我不是很明白【100分】
世紀公元和年代的演算法 本世紀初，美國物理學會(American Institute of Physics)和IEEE計算機社團 (IEEE Computer Society)的一本聯合刊物《科學與工程中的計算》發表了由田納西大學的Jack Dongarra和橡樹嶺國家實驗室的Francis Sullivan 聯名撰寫的「世紀十大演算法」一文，該文「試圖整理出在20世紀對科學和工程領域的發展產生最大影響力的十大演算法」。作者苦於「任何選擇都將是充滿爭議的， 因為實在是沒有最好的演算法」，他們只好用編年順序依次列出了這十項演算法領域人類智慧的巔峰之作——給出了一份沒有排名的演算法排行榜。有趣的是，該期雜志還 專門邀請了這些演算法相關領域的「大拿」為這十大演算法撰寫十篇綜述文章，實在是蔚為壯觀。本文的目的，便是要帶領讀者走馬觀花，一同回顧當年這一演算法界的盛 舉。
1946 蒙特卡洛方法
在廣場上畫一個邊長一米的正方形，在正方形內部隨意用粉筆畫一個不規則的形 狀，呃，能幫我算算這個不規則圖形的面積么？蒙特卡洛(Monte Carlo)方法便是解決這個問題的巧妙方法:隨機向該正方形內扔N（N 是一個很大的自然數）個黃豆，隨後數數有多少個黃豆在這個不規則幾何形狀內部，比如說有M個:那麼，這個奇怪形狀的面積便近似於M/N，N越大，算出來的 值便越精確。別小看這個數黃豆的笨辦法，大到國家的民意測驗，小到中子的移動軌跡，從金融市場的風險分析，到軍事演習的沙盤推演，蒙特卡洛方法無處不在背 後發揮著它的神奇威力。
蒙特卡洛方法由美國拉斯阿莫斯國家實驗室的三位科學家John von Neumann（看清楚了，這位可是馮諾伊曼同志！）,Stan Ulam 和 Nick Metropolis共同發明。就其本質而言，蒙特卡洛方法是用類似於物理實驗的近似方法求解問題，它的魔力在於，對於那些規模極大的問題，求解難度隨著 問題的維數（自變數個數）的增加呈指數級別增長，出現所謂的「維數的災難」（Course of Dimensionality）。對此，傳統方法無能為力，而蒙特卡洛方法卻可以獨辟蹊徑，基於隨機模擬的過程給出近似的結果。
最後八卦一下，Monte Carlo這個名字是怎麼來的？它是摩納哥的一座以博彩業聞名的城市，賭博其實是門概率的高深學問，不是么？
1947 單純形法
單 純形法是由大名鼎鼎的「預測未來」的蘭德公司的Grorge Dantzig發明的，它成為線性規劃學科的重要基石。所謂線性規劃，簡單的說，就是給定一組線性（所有變數都是一次冪）約束條件（例如a1*x1+ b1*x2+c1*x3>0)，求一個給定的目標函數的極值。這么說似乎也太太太抽象了，但在現實中能派上用場的例子可不罕見——比如對於一個公司 而言，其能夠投入生產的人力物力有限（「線性約束條件」），而公司的目標是利潤最大化（「目標函數取最大值」），看，線性規劃並不抽象吧！線性規劃作為運 籌學(operation research)的一部分，成為管理科學領域的一種重要工具。而Dantzig提出的單純形法便是求解類似線性規劃問題的一個極其有效的方法，說來慚 愧，本科二年級的時候筆者也學過一學期的運籌學，現在腦子里能想起的居然只剩下單純形法了——不過這不也正說明了該方法的簡單和直觀么？
順便說句題外話，寫過《萬曆十五年》的黃仁宇曾說中國的傳統是「不能從數目字上管理」，我們習慣於「拍腦袋」，而不是基於嚴格的數據做決定，也許改變這一傳統的方法之一就是全民動員學習線性規劃喔。
1950 Krylov子空間迭代法
1951 矩陣計算的分解方法
50 年代初的這兩個演算法都是關於線性代數中的矩陣計算的，看到數學就頭大的讀者恐怕看到演算法的名字已經開始皺眉毛了。Krylov子空間疊代法是用來求解形如 Ax=b 的方程，A是一個n*n 的矩陣，當n充分大時，直接計算變得非常困難，而Krylov方法則巧妙地將其變為Kxi+1=Kxi+b-Axi的迭代形式來求解。這里的K(來源於作 者俄國人Nikolai Krylov姓氏的首字母)是一個構造出來的接近於A的矩陣，而迭代形式的演算法的妙處在於，它將復雜問題化簡為階段性的易於計算的子步驟。
1951年由橡樹嶺國家實驗室的AlstonHouseholder提出的矩陣計算的分解方法，則證明了任何矩陣都可以分解為三角、對角、正交和其他特殊形式的矩陣，該演算法的意義使得開發靈活的矩陣計算軟體包成為可能。
1957 優化的Fortran編譯器
說 實話，在這份學術氣息無比濃郁的榜單里突然冒出一個編譯器(Compiler)如此工程化的東東實在讓人有「關公戰秦瓊」的感覺。不過換個角度想 想，Fortran這一門幾乎為科學計算度身定製的編程語言對於科學家（尤其是數學家，物理學家）們實在是太重要了，簡直是他們形影不離的一把瑞士軍刀， 這也難怪他們紛紛搶著要把票投給了它。要知道，Fortran是第一種能將數學公式轉化為計算機程序的高級語言，它的誕生使得科學家們真正開始利用計算機 作為計算工具為他們的研究服務，這是計算機應用技術的一個里程碑級別的貢獻。
話說回來，當年這幫開發Fortran的傢伙真是天 才——只用23500行匯編指令就完成了一個Fortran編譯器，而且其效率之高令人嘆為觀止:當年在IBM 主持這一項目的負責人JohnBackus在數十年後，回首這段往事的時候也感慨，說它生成代碼的效率「出乎了所有開發者的想像」。看來作為程序員，自己 寫的程序跑起來「出乎自己的想像」，有時候還真不一定是件壞事！
1959-61 計算矩陣特徵值的QR演算法
呼， 又是一個和線性代數有關的演算法，學過線性代數的應該還記得「矩陣的特徵值」吧？計算特徵值是矩陣計算的最核心內容之一，傳統的求解方案涉及到高次方程求 根，當問題規模大的時候十分困難。QR演算法把矩陣分解成一個正交矩陣（什麼是正交矩陣？！還是趕緊去翻書吧！）與一個上三角矩陣的積，和前面提到的 Krylov 方法類似，這又是一個迭代演算法，它把復雜的高次方程求根問題化簡為階段性的易於計算的子步驟，使得用計算機求解大規模矩陣特徵值成為可能。這個演算法的作者 是來自英國倫敦的J.G.F. Francis。
1962 快速排序演算法
不少讀者恐怕和我一樣,看到「快 速排序演算法」（Quick Sort）這個條目時,心裡的感覺是——「這可總算找到組織了」。相比於其他一些對程序員而言高深莫測的數學物理公式,快速排序演算法真是我們朝夕相處的好 夥伴——老闆讓你寫個排序演算法,如果你寫出來的不是快速排序,你都不好意思跟同事打招呼。其實根本不用自己動手實現, 不論是ANSI C,C++ STL,還是Java SDK,天下幾乎所有的SDK里都能找到它的某種實現版本。
快速排序演算法最早由Tony Hoare爵士設計，它的基本思想是將待排序列分為兩半，左邊的一半總是「小的」，右邊的一半總是「大的」，這一過程不斷遞歸持續下去，直到整個序列有 序。說起這位Tony Hoare爵士，快速排序演算法其實只是他不經意間的小小發現而已，他對於計算機貢獻主要包括形式化方法理論，以及ALGOL60 編程語言的發明等，他也因這些成就獲得1980 年圖靈獎。
快速排序的平均時間復雜度僅僅為O(Nlog(N))，相比於普通選擇排序和冒泡排序等而言，實在是歷史性的創舉。
1965 快速傅立葉變換
如 果要評選對我們的日常生活影響最大的演算法，快速傅立葉變換演算法應該是當仁不讓的總冠軍——每天當拿起話筒，打開手機，聽mp3，看DVD，用DC拍照 ——毫不誇張的說，哪裡有數字信號處理，哪裡就有快速傅立葉變換。快速傅立葉演算法是離散傅立葉演算法（這可是數字信號處理的基石）的一種快速演算法，它有 IBM 華生研究院的James Cooley和普林斯頓大學的John Tukey共同提出，其時間復雜度僅為O(Nlog(N))；比時間效率更為重要的是，快速傅立葉演算法非常容易用硬體實現，因此它在電子技術領域得到極其 廣泛的應用。
1977 整數關系探測演算法
整數關系探測是個古老的問題，其歷史甚至可以追溯到歐幾里德的時代。具體的說:
給 定—組實數X1,X2,...,Xn，是否存在不全為零的整數a1,a2,...an，使得:a 1 x 1 +a 2 x 2 + . . . + a n x n ＝ 0 這一年BrighamYoung大學的Helaman Ferguson 和Rodney Forcade解決了這一問題。至於這個演算法的意義嘛，呃，該演算法應用於「簡化量子場論中的Feynman圖的計算」——太深奧的學問拉！
1987 快速多極演算法
日 歷翻到了1987 年，這一年的演算法似乎更加玄奧了，耶魯大學的Leslie Greengard和Vladimir Rokhlin提出的快速多極演算法用來計算「經由引力或靜電力相互作用的N 個粒子運動的精確計算——例如銀河系中的星體，或者蛋白質中的原子間的相互作用」，天哪，不是我不明白，這世界真是變得快！
所謂浪花淘盡英雄，這些演算法的發明者許多已經駕鶴西去。二十一世紀的頭五年也已經在不知不覺中從我們指尖滑過，不知下一次十大演算法評選的盛事何時再有，也許我們那時已經垂垂老去，也許我們早已不在人世，只是心中唯一的希望——裡面該有個中國人的名字吧！