比較式演算法

A. 比較Dijkstra演算法與Floyd演算法。

（1）Dijkstra演算法：在網路中用得多，一個一個節點添加，加一個點刷一次路由表。

Dijkstra演算法是典型的演算法。Dijkstra演算法是很有代表性的演算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。

（2）Floyd演算法：把所有已經連接的路徑都標出來，再通過不等式比較來更改路徑。

Floyd演算法又稱為插點法，是一種用於尋找給定的加權圖中多源點之間最短路徑的演算法。該演算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。

B. 冒泡排序法和快速排序比較的演算法

打你屁股，這么簡單的問題都不認真研究一下。

冒泡排序是最慢的排序，時間復雜度是 O(n^2)。

快速排序是最快的排序。關於快速排序，我推薦你看看《代碼之美》第二章：我編寫過的最漂亮的代碼。作者所說的最漂亮，就是指效率最高的。

--------------------------------摘自《代碼之美》---------------

當我撰寫關於分治（divide-and-conquer）演算法的論文時，我發現C.A.R. Hoare的Quicksort演算法（「Quicksort」，Computer Journal 5）無疑是各種Quicksort演算法的鼻祖。這是一種解決基本問題的漂亮演算法，可以用優雅的代碼實現。我很喜歡這個演算法，但我總是無法弄明白演算法中最內層的循環。我曾經花兩天的時間來調試一個使用了這個循環的復雜程序，並且幾年以來，當我需要完成類似的任務時，我會很小心地復制這段代碼。雖然這段代碼能夠解決我所遇到的問題，但我卻並沒有真正地理解它。
我後來從Nico Lomuto那裡學到了一種優雅的劃分（partitioning）模式，並且最終編寫出了我能夠理解，甚至能夠證明的Quicksort演算法。William Strunk Jr.針對英語所提出的「良好的寫作風格即為簡練」這條經驗同樣適用於代碼的編寫，因此我遵循了他的建議，「省略不必要的字詞」（來自《The Elements of Style》一書）。我最終將大約40行左右的代碼縮減為十幾行的代碼。因此，如果要回答「你曾編寫過的最漂亮代碼是什麼？」這個問題，那麼我的答案就是：在我編寫的《Programming Pearls, Second Edition》(Addison-Wesley)一書中給出的Quichsort演算法。在示例2-1中給出了用c語言編寫的Quicksort函數。我們在接下來的章節中將進一步地研究和改善這個函數。
【示例】 2-1 Quicksort函數
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return; 10
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
如果函數的調用形式是quicksort(0, n-1)，那麼這段代碼將對一個全局數組x[n]進行排序。函數的兩個參數分別是將要進行排序的子數組的下標：l是較低的下標，而u是較高的下標。函數調用swap(i,j)將會交換x[i]與x[j]這兩個元素。第一次交換操作將會按照均勻分布的方式在l和u之間隨機地選擇一個劃分元素。
在《Programming Pearls》一書中包含了對Quicksort演算法的詳細推導以及正確性證明。在本章的剩餘內容中，我將假設讀者熟悉在《Programming Pearls》中所給出的Quicksort演算法以及在大多數初級演算法教科書中所給出的Quicksort演算法。
如果你把問題改為「在你編寫那些廣為應用的代碼中，哪一段代碼是最漂亮的？」我的答案還是Quicksort演算法。在我和M. D. McIlroy一起編寫的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原來Unix qsort函數中的一個嚴重的性能問題。隨後，我們開始用C語言編寫一個新排序函數庫，並且考慮了許多不同的演算法，包括合並排序（Merge Sort）和堆排序（Heap Sort）等演算法。在比較了Quicksort的幾種實現方案後，我們著手創建自己的Quicksort演算法。在這篇文章中描述了我們如何設計出一個比這個演算法的其他實現要更為清晰，速度更快以及更為健壯的新函數——部分原因是由於這個函數的代碼更為短小。Gordon Bell的名言被證明是正確的：「在計算機系統中，那些最廉價，速度最快以及最為可靠的組件是不存在的。」現在，這個函數已經被使用了10多年的時間，並且沒有出現任何故障。
考慮到通過縮減代碼量所得到的好處，我最後以第三種方式來問自己在本章之初提出的問題。「你沒有編寫過的最漂亮代碼是什麼？」。我如何使用非常少的代碼來實現大量的功能？答案還是和Quicksort有關，特別是對這個演算法的性能分析。我將在下一節給出詳細介紹。
2.2 事倍功半
Quicksort是一種優雅的演算法，這一點有助於對這個演算法進行細致的分析。大約在1980年左右，我與Tony Hoare曾經討論過Quicksort演算法的歷史。他告訴我，當他最初開發出Quicksort時，他認為這種演算法太簡單了，不值得發表，而且直到能夠分析出這種演算法的預期運行時間之後，他才寫出了經典的「Quicksoft」論文。
我們很容易看出，在最壞的情況下，Quicksort可能需要n2的時間來對數組元素進行排序。而在最優的情況下，它將選擇中值作為劃分元素，因此只需nlgn次的比較就可以完成對數組的排序。那麼，對於n個不同值的隨機數組來說，這個演算法平均將進行多少次比較？
Hoare對於這個問題的分析非常漂亮，但不幸的是，其中所使用的數學知識超出了大多數程序員的理解范圍。當我為本科生講授Quicksort演算法時，許多學生即使在費了很大的努力之後，還是無法理解其中的證明過程，這令我非常沮喪。下面，我們將從Hoare的程序開
11
始討論，並且最後將給出一個與他的證明很接近的分析。
我們的任務是對示例2-1中的Quicksort代碼進行修改，以分析在對元素值均不相同的數組進行排序時平均需要進行多少次比較。我們還將努力通過最短的代碼、最短運行時間以及最小存儲空間來得到最深的理解。
為了確定平均比較的次數，我們首先對程序進行修改以統計次數。因此，在內部循環進行比較之前，我們將增加變數comps的值（參見示例2-2）。
【示例2-2】 修改Quicksort的內部循環以統計比較次數。
for (i = l+1; i <= u; i++) {
comps++;
if (x[i] < x[l])
swap(++m, i);
}
如果用一個值n來運行程序，我們將會看到在程序的運行過程中總共進行了多少次比較。如果重復用n來運行程序，並且用統計的方法來分析結果，我們將得到Quicksort在對n個元素進行排序時平均使用了1.4 nlgn次的比較。
在理解程序的行為上，這是一種不錯的方法。通過十三行的代碼和一些實驗可以反應出許多問題。這里，我們引用作家Blaise Pascal和T. S. Eliot的話，「如果我有更多的時間，那麼我給你寫的信就會更短。」現在，我們有充足的時間，因此就讓我們來對代碼進行修改，並且努力編寫出更短（同時更好）的程序。
我們要做的事情就是提高這個演算法的速度，並且盡量增加統計的精確度以及對程序的理解。由於內部循環總是會執行u-l次比較，因此我們可以通過在循環外部增加一個簡單的操作來統計比較次數，這就可以使程序運行得更快一些。在示例2-3的Quicksort演算法中給出了這個修改。
【示例2-3】 Quicksort的內部循環，將遞增操作移到循環的外部
comps += u-l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
這個程序會對一個數組進行排序，同時統計比較的次數。不過，如果我們的目標只是統計比較的次數，那麼就不需要對數組進行實際地排序。在示例2-4中去掉了對元素進行排序的「實際操作」，而只是保留了程序中各種函數調用的「框架」。
【示例2-4】將Quicksort演算法的框架縮減為只進行統計
void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
12
這個程序能夠實現我們的需求，因為Quichsort在選擇劃分元素時採用的是「隨機」方式，並且我們假設所有的元素都是不相等的。現在，這個新程序的運行時間與n成正比，並且相對於示例2-3需要的存儲空間與n成正比來說，現在所需的存儲空間縮減為遞歸堆棧的大小，即存儲空間的平均大小與lgn成正比。
雖然在實際的程序中，數組的下標（l和u）是非常重要的，但在這個框架版本中並不重要。因此，我們可以用一個表示子數組大小的整數(n)來替代這兩個下標（參見示例2-5）
【示例2-5】 在Quicksort代碼框架中使用一個表示子數組大小的參數
void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
現在，我們可以很自然地把這個過程整理為一個統計比較次數的函數，這個函數將返回在隨機Quicksort演算法中的比較次數。在示例2-6中給出了這個函數。
【示例2-6】 將Quicksort框架實現為一個函數
int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
在示例2-4、示例2-5和示例2-6中解決的都是相同的基本問題，並且所需的都是相同的運行時間和存儲空間。在後面的每個示例都對這些函數的形式進行了改進，從而比這些函數更為清晰和簡潔。
在定義發明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)時，George Póllya指出「計劃越宏大，成功的可能性就越大。」現在，我們就來研究在分析Quicksort時的矛盾。到目前為止，我們遇到的問題是，「當Quicksort對大小為n的數組進行一次排序時，需要進行多少次比較？」我們現在將對這個問題進行擴展，「對於大小為n的隨機數組來說，Quichsort演算法平均需要進行多少次的比較？」我們通過對示例2-6進行擴展以引出示例2-7。
【示例2-7】 偽碼：Quicksort的平均比較次數
float c(int n)
if (n <= 1) return 0
sum = 0
for (m = 1; m <= n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
如果在輸入的數組中最多隻有一個元素，那麼Quichsort將不會進行比較，如示例2-6
13
中所示。對於更大的n，這段代碼將考慮每個劃分值m（從第一個元素到最後一個，每個都是等可能的）並且確定在這個元素的位置上進行劃分的運行開銷。然後，這段代碼將統計這些開銷的總和（這樣就遞歸地解決了一個大小為m-1的問題和一個大小為n-m的問題），然後將總和除以n得到平均值並返回這個結果。
如果我們能夠計算這個數值，那麼將使我們實驗的功能更加強大。我們現在無需對一個n值運行多次來估計平均值，而只需一個簡單的實驗便可以得到真實的平均值。不幸的是，實現這個功能是要付出代價的：這個程序的運行時間正比於3n（如果是自行參考（self-referential）的，那麼用本章中給出的技術來分析運行時間將是一個很有趣的練習）。
示例2-7中的代碼需要一定的時間開銷，因為它重復計算了中間結果。當在程序中出現這種情況時，我們通常會使用動態編程來存儲中間結果，從而避免重復計算。因此，我們將定義一個表t[N+1]，其中在t[n]中存儲c[n]，並且按照升序來計算它的值。我們將用N來表示n的最大值，也就是進行排序的數組的大小。在示例2-8中給出了修改後的代碼。
【示例2-8】 在Quicksort中使用動態編程來計算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += n-1 + t[i-1] + t[n-i]
t[n] = sum/n
這個程序只對示例2-7進行了細微的修改，即用t[n]來替換c(n)。它的運行時間將正比於N2，並且所需的存儲空間正比於N。這個程序的優點之一就是：在程序執行結束時，數組t中將包含數組中從元素0到元素N的真實平均值（而不是樣本均值的估計）。我們可以對這些值進行分析，從而生成在Quichsort演算法中統計比較次數的計算公式。
我們現在來對程序做進一步的簡化。第一步就是把n-1移到循環的外面，如示例2-9所示。
【示例2-9】 在Quicksort中把代碼移到循環外面來計算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += t[i-1] + t[n-i]
t[n] = n-1 + sum/n
現在將利用對稱性來對循環做進一步的調整。例如，當n為4時，內部循環計算總和為：
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
在上面這些組對中，第一個元素增加而第二個元素減少。因此，我們可以把總和改寫為：
2 * (t[0] + t[1] + t[2] + t[3])
我們可以利用這種對稱性來得到示例2-10中的Quicksort。
【示例2-10】 在Quichsort中利用了對稱性來計算
t[0] = 0
14
for (n = 1; n <= N; n++)
sum = 0
for (i = 0; i < n; i++)
sum += 2 * t[i]
t[n] = n-1 + sum/n
然而，在這段代碼的運行時間中同樣存在著浪費，因為它重復地計算了相同的總和。此時，我們不是把前面所有的元素加在一起，而是在循環外部初始化總和並且加上下一個元素，如示例2-11所示。
【示例2-11】 在Quicksort中刪除了內部循環來計算
sum = 0; t[0] = 0
for (n = 1; n <= N; n++)
sum += 2*t[n-1]
t[n] = n-1 + sum/n
這個小程序確實很有用。程序的運行時間與N成正比，對於每個從1到N的整數，程序將生成一張Quicksort的估計運行時間表。
我們可以很容易地把示例2-11用表格來實現，其中的值可以立即用於進一步的分析。在2-1給出了最初的結果行。
表2-1 示例2-11中實現的表格輸出
N Sum t[n]
0 0 0
1 0 0
2 0 1
3 2 2.667
4 7.333 4.833
5 17 7.4
6 31.8 10.3
7 52.4 13.486
8 79.371 16.921
這張表中的第一行數字是用代碼中的三個常量來進行初始化的。下一行（輸出的第三行）的數值是通過以下公式來計算的：
A3 = A2+1 B3 = B2 + 2*C2 C3 = A2-1 + B3/A3
把這些（相應的）公式記錄下來就使得這張表格變得完整了。這張表格是「我曾經編寫的最漂亮代碼」的很好的證據，即使用少量的代碼完成大量的工作。
但是，如果我們不需要所有的值，那麼情況將會是什麼樣？如果我們更希望通過這種來方式分析一部分數值（例如，在20到232之間所有2的指數值）呢？雖然在示例2-11中構建了完整的表格t，但它只需要使用表格中的最新值。因此，我們可以用變數t的定長空間來替代table t[]的線性空間，如示例2-12所示。
【示例2-12】 Quicksoft 計算——最終版本
sum = 0; t = 0
15
for (n = 1; n <= N; n++)
sum += 2*t
t = n-1 + sum/n
然後，我們可以插入一行代碼來測試n的適應性，並且在必要時輸出這些結果。
這個程序是我們漫長學習旅途的終點。通過本章所採用的方式，我們可以證明Alan Perlis的經驗是正確的：「簡單性並不是在復雜性之前，而是在復雜性之後」 ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9)。

C. 光強對比度的計算公式

光強對比度的演算法公式：一副圖像的亮度對比度調節屬於圖像的灰度線性變換，其公式如下:y = [x - 127.5 * (1 - B)] * k + 127.5 * (1 + B)；x為調節前的像素值，y為調節後的像素值。

其中B取值[-1,1]，調節亮度；k調節對比度，arctan(k)取值[1,89]，所以k = tan( (45 + 44 * c) / 180 * pi )；其中c取值[-1,1]。

對比度指的是一幅圖像中明暗區域最亮的白和最暗的黑之間不同亮度層級的測量，差異范圍越大代表對比越大，差異范圍越小代表對比越小，好的對比率120:1就可容易地顯示生動、豐富的色彩，當對比率高達300:1時，便可支持各階的顏色。

視覺影響

對比度對視覺效果的影響非常關鍵，一般來說對比度越大，圖像越清晰醒目，色彩也越鮮明艷麗；而對比度小，則會讓整個畫面都灰濛蒙的。

高對比度對於圖像的清晰度、細節表現、灰度層次表現都有很大幫助。在一些黑白反差較大的文本顯示、CAD顯示和黑白照片顯示等方面，高對比度產品在黑白反差、清晰度、完整性等方面都具有優勢。

相對而言，在色彩層次方面，高對比度對圖像的影響並不明顯。對比度對於動態視頻顯示效果影響要更大一些，由於動態圖像中明暗轉換比較快，對比度越高，人的眼睛越容易分辨出這樣的轉換過程。

D. 各種查找演算法的比較

二分法平均查找效率是O(logn)，但是需要數組是排序的。如果沒有排過序，就只好先用O（nlogn)的預處理為它排個序了。而且它的插入比較困難，經常需要移動整個數組，所以動態的情況下比較慢。

哈希查找理想的插入和查找效率是O(1)，但條件是需要找到一個良好的散列函數，使得分配較為平均。另外，哈希表需要較大的空間，至少要比O(n)大幾倍，否則產生沖突的概率很高。

二叉排序樹查找也是O(logn)的，關鍵是插入值時需要做一些處理使得它較為平衡（否則容易出現輕重的不平衡，查找效率最壞會降到O(n)），而且寫起來稍微麻煩一些，具體的演算法你可以隨便找一本介紹數據結構的書看看。當然，如果你用的是c語言，直接利用它的庫類型map、multimap就可以了,它是用紅黑樹實現的，理論上插入、查找時間都是O(logn)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。

E. 跪求多項式遺傳編程擬合曲線的代碼！！！

http://www.51kaifa.com/jswz/read.php?ID=1326

多項式可用於非線性信號的擬合，關鍵在於求解其各項系數。對於任何非線性函數，文中提出都有一個規范化的擬合方法。相應有一個規范化的多項式。該規范化多項式是以整數n為底的冪級數，最大冪次 nmax是x坐標區間的等分數，其系數可用一個規范化的矩陣積得到。文中又給出了固體電子學中的兩個應用實例。當x坐標區間分段擬合應用時，還討論了函數及其導數計算值的連續性條件，並以正弦函數不同區間的展開為例，作了演示。
[關鍵詞] 多項式擬合，非線性信號，規范化方法，規范化矩陣

物理或化學量之間的非線性關系已受到廣泛的重視。比較廣泛應用的擬合方法是最小二乘法〔1〕，還有神經網路法〔2〕, 遺傳演算法〔3〕，退火演算法〔4〕等。都是針對某一實際問題採用的方法。其中最小二乘法又分為最佳擬合直線(最小二乘擬合直線，端點直線和零基準最小二乘擬合直線)和最佳多項式擬合曲線。前者的優點是用一個正比直線代替曲線給計算帶來許多方便。後者的精度明顯比前者高。因此精度要求比較高的場合通常採用多項式擬合。

1 基本原理
有一非線性信號y=f(x)可以用一個多項式來表示
通常取到n=4便可以是近似表達非劇變的非多極值的單值關系。即有
ε為小量。
如何得到多項式各個系數成為解決問題的關鍵。這就有上面所提到各種方法。對於式(2)來說，一般需要有4次測量值即曲線上的四個點(如圖1所示)

方可得到 。時，便相應有

這里張量的右上角標指標代表方階，第2個右下標則是列指標，兩者相同。 取決於所測物理量的大小，與具體問題有關。因此求解便不能用一種標准化的方法。現在提出一種規范的方法，也就是說，不管什麼問題， 都可以轉化為一種規范化的同構矩陣及相應的逆矩陣。這為非線性的問題採用多項式擬合提供了極大的方便。
令xn=nx1 , (5)
n為整數。即有等分點被稱為橫坐標的縮尺。例如取n=4,則有x1=xmax/4。於是有 ：

可以得到下式：

其中n=x/x1,比較式(7)和 (10)可以得到
由式(2)，即 就是式(9)，可見這是一種標准演算法，與x物理量無關，這是本文所追求的目標。與物理量有關的僅僅是其縮尺x1。

2. 應用實例
集成電路生產中經常要使用Van der Pauw和Rymaszewsk法測定薄層電阻。前者用下式[5]：

於是范德堡函數可以表示為

上式的曲線如圖2所示，與ASTM中的曲線(圖2中虛線)十分吻合[7]。式(14)在 ＝1到10的范圍內的精度為

3. 討論
上面已討論了n=5時非線性函數展開式5階多項式的情況。取5個等分點便可以實現精確的擬合。如果已得n=8等分點上非線性函數的單值。希望多項式展開到四階，則分成二大段展開：
同樣可以應用本文所介紹的多項式進行規范化擬合。可以看出，擬合的精度取決於非線性函數自身的光滑程度以及起伏變化的大小等分點的密集程度。等分點越密集，則規范化矩陣的階數越高，求其逆矩陣越繁瑣。因此，可以進行如上面所述的分段擬合，以降低矩陣的階數。
3.1 分段計算時接合點上的函數連續性問題
只要 矩陣元的小數點位足夠精確，在分段接合點 上，函數值肯定是連續的。即有：

證明從略。

3.2 分段計算時接合點上的導數的連續性問題

由4.1討論可知y3、y4、y5， 可以嚴格保持原始值，導數在 (即x4點)的連續性就取決於他們的原始分布。圖3中a、b、c表示出三種情況下y3、y4、y5的分布。除了第三種情況外，第一二兩種情況是在一級近似下分段計算的導數是連續的。當要求導數在接合點連續時，擬合的相鄰分段就應該有部分重疊。這時y(1)和y(2)做多項式擬合時橫坐標就分成5或6等分。相應展開成5階或6階冪級數。在接合點x4上的導數在一級近似下就可取其左右兩邊的導數的平均值：

因此，即使出現了圖3-c情況，導數也是連續的。為了說明上述做法的可行性，下面以非線性函數sin(x)及其導數為例來加以印證。將x坐標的等分點取為 這就代表一個起伏變化的函數，有推廣應用價值。現讓二分段有部分重疊，用上面介紹的規范化方法分別得到二分段的多項式擬合結果：

圖4示出各擬合式的曲線與sin(x)曲線的比較，以觀察兩者接近情況以及接合點上函數連續情況。圖5示出上述擬合式的導數與sin(x)ˊ=cosx 曲線的比較。可見導數也是連續的。總之，本文所提出的方法方便，簡單，擬合精度高，標准規范的特點。當擬合點多時，為降低矩陣的階數，可以分段擬合。只要逆矩陣元的小數位足夠精確，接合點上擬合式肯定連續。當兩段間有部分重疊時，導數也是連續的。

參考文獻

[1] 孫以材，劉玉嶺，孟慶浩，壓力感測器的設計製造與應用，(北京)冶金工業出版社(2000)
[2] 王偉，人工神經網路原理，北京航空航天出版社(1995)
[3] Helena Szezerbicka and Matthias Becker,Genetic Algorithms : A tool for modeling simulation and optimization of complex system . Cybernetics and systems : An International Journal , 1998 , 29 : 639-659 .
[4] 姚姚，蒙特卡洛非線性反演方法及應用，(北京)冶金工業出版社(1997).
[5] L. J. van der pauw, Philips Research Reports 13(1958), 1.
[6] Rymaszewski R., Electron. Lett. , 3 (1967), 57.
[7] ASTM F76-68,1971 Annual book,part 8,P652-668