第一章 所有

1.1-1給出顯示生活中需要排序的一個例子或顯示生活中需要計算凸殼的一個例子

凸殼可以看作是點集合的邊界，其精确定義如下：

設集合S是n維空間的k個點組成的集合，即S={x1,x2,…xk},xi是n維向量。定義S的凸殼Conv(S)為：

Conv(S)={x=λ1*x1+λ2*x2+…+λk*xk | λ1+λ2+ …+λk=1}

1）大個在前小個在後排序O(∩_∩)O，從小到大聽了好多遍哒。

2）某個十字路口，不同的汽車以不同的機率到達，到達的總機率為1，不同汽車到達後的行駛時間也不同，問十字路口平均每輛車的機率。

1.1-2除速度外，再真是環境中還可能使用哪些其他有關效率的度量？

功率、水流速度、帶寬（世界是運動的）

1.1-3選擇一種你以前已知的資料結構，并讨論其優勢和局限

冒泡排序

優勢：正序的時候比較一次就出結果。

劣勢：逆序的時候比較（n+1）n/2次出結果

1.1-4 前面給出的最短路徑與旅行商問題有哪些相似之處？又有哪些不同？

旅行商問題（Traveling Salesman Problem，TSP）又譯為旅行推銷員問題、貨郎擔問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之後，最後再回到原點的最小路徑成本。

相似之處：都存在許多候選解，但絕大多數候選解都沒有解決手頭的問題。尋找一個真正的解或一個最好的解可能是一個很大的挑戰。

不同之處：最短路徑隻要找出路徑最短即可，但像旅行商這樣的問題，要考慮的因素不止是最短路徑一個，并沒有一個容易識别的候選解集。

1.1-5提供一個現實生活的問題，其中隻有最佳解才行。然後提供一個問題，其中近似最佳的一個解也足夠好。

最佳解：求兩地的最短路徑（兩點之間直線最短）

近似最佳解：最經濟可行的路徑

1.2-1給出在應用層需要算法内容的應用的一個例子，并讨論涉及的算法的功能。

圖形使用者界面的畫圖，小遊戲的實作，萬事皆算法。算法的功能：提供解決問題的方法，減少備援，提高效率，并存在一定的規律行，邏輯上存在條理。

1.2-2假設我們正比較插入排序與歸并排序在相同機器上的實作。對規模為n的輸入，插入排序運作 8n2 步，而歸并排序運作 64nlgn 步。問對哪些n值，插入排序優于歸并排序。

當n>43時候成立， 8n2<64nlgn 解方程即可。

1.2-3 n的最小值為何值時，運作時間為 100n2 的一個算法在相同機器上快于運作時間為 2n 的另一算法？

100n2 = 2n 解方程，n=15時候成立。