一弦追、目標(biāo)：計(jì)算
??整個(gè)計(jì)算機(jī)科學(xué)的目的劲件，都是為了實(shí)現(xiàn)高效和低耗的計(jì)算。為了理解什么是計(jì)算牵辣，我們首先來(lái)看幾個(gè)實(shí)例躺枕。
Fig. 1 實(shí)例：繩索計(jì)算
Fig. 2 實(shí)例：尺規(guī)計(jì)算機(jī)
1.1 定義算法
??計(jì)算服猪，就是借助某種工具供填，遵照一定規(guī)則拐云，以明確而機(jī)械的形式進(jìn)行罢猪。計(jì)算模型（計(jì)算機(jī)）就是計(jì)算中使用的工具。
??算法叉瘩，即在特定計(jì)算模型下膳帕，旨在解決特定問(wèn)題的指令序列。
- 特點(diǎn)：
①輸入、輸出明確
②正確性（可解決問(wèn)題）
③確定性（任意算法都可描述為一個(gè)由基本操作注組成的序列）
④可行性 （每一基本操作都可實(shí)現(xiàn)）
⑤有窮性 （對(duì)于任何輸入，經(jīng)過(guò)有窮次計(jì)算后終止）
- 如何理解”有窮性“？
Fig. 3 Hailstone序列
例子:
Hailstone序列一定會(huì)呈現(xiàn)出整體下降的趨勢(shì)，盡管中間可能會(huì)飄忽不定。
#include<iostream>
int len_hailstone(int n){
int length = 0;
std::cout<<n<<", ";
while(n>1){(n%2) ? n=n*3+1 : n/=2;std::cout<<n<<", "; length++;}
std::cout<<std::endl;
return length;
}
int main(int argc, char* argv[]){
auto n = atoi(argv[1]);
std::cout<<"length of hailstone("<<n<<"): "<<len_hailstone(n)<<std::endl;
return 0;
}
? Chapter1 ./hailstone 27
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1,
length of hailstone{27}: 111
- 問(wèn)題：對(duì)于任意n， 序列的長(zhǎng)度是否是有窮的？
- 答案：不確定。這個(gè)序列的長(zhǎng)度未必是有限的。因此上面的程序未必可以稱(chēng)為一個(gè)“算法”坟募。
- 什么是好算法
??對(duì)算法來(lái)說(shuō)最重要的特征：效率
1.2 計(jì)算模型
??如何評(píng)價(jià)不同DSA的效率: 度量。 ( If you cannot measure it, you can not improve it. )
-
測(cè)度：
Fig. 5 用某個(gè)實(shí)例的計(jì)算成本來(lái)評(píng)價(jià)DSA的效率是不現(xiàn)實(shí)的 - 分析：?jiǎn)栴}實(shí)例的規(guī)模围详，往往是決定計(jì)算成本的主要因素（正相關(guān)）
- 最壞情況分析原則：對(duì)于規(guī)模為n的所有實(shí)例中雹食，只關(guān)注最壞（成本最高）者
1.2.1 圖靈機(jī)模型
Fig. 6 圖靈機(jī)概念
-
實(shí)例：通過(guò)圖靈機(jī)完成非負(fù)整數(shù)加一的功能埠通。
Fig. 7
1.2.2 RAM模型
Fig. 8. RAM模型及其指令集
- 重點(diǎn)：這些模型將算法的運(yùn)行時(shí)間轉(zhuǎn)換為基本操作的次數(shù)來(lái)評(píng)價(jià)众雷，從而將DSA的評(píng)價(jià)和單次實(shí)驗(yàn)的各種環(huán)境因素分離開(kāi)。具體來(lái)說(shuō)悯嗓，每個(gè)算法的流程應(yīng)該是清晰临梗、可羅列红淡，且沒(méi)有歧義的遂黍。這就為評(píng)價(jià)算法提供了基礎(chǔ)。
二带到、復(fù)雜度分析
2.1 大
記號(hào)
??大記號(hào)可以看做評(píng)價(jià)DSA的一把直尺闪金，其刻度并不精細(xì)损俭，而是主要用于評(píng)價(jià)DSA的“潛力”，比如它在求解大規(guī)模問(wèn)題時(shí)的性能鼻听。更確切的說(shuō)，大
記號(hào)關(guān)注的是隨著n的增長(zhǎng)(n>>2)，算法成本的增長(zhǎng)趨勢(shì)。
Fig. 9. 大O記號(hào)
??大記號(hào)的處理手法:
- 常系數(shù)可忽略
- 低次項(xiàng)可忽略
2.1.1 常數(shù)復(fù)雜度)
?? 。這類(lèi)算法的效率最高返弹。
2.1.2 對(duì)數(shù)復(fù)雜度)
常底數(shù)和常數(shù)次冪無(wú)所謂：
??①
??②
- 這類(lèi)算法無(wú)限接近于
丐巫，非常令人滿(mǎn)意祝闻。
2.1.3 多項(xiàng)式復(fù)雜度 )
??多項(xiàng)式的最高此項(xiàng)即為復(fù)雜度
- 線(xiàn)性復(fù)雜度:
： 代表線(xiàn)性函數(shù)堤框。很多編程題復(fù)雜度都介乎
委可。
2.1.4 指數(shù)復(fù)雜度 )
??這類(lèi)算法的計(jì)算成本增長(zhǎng)的極快崇决，通常認(rèn)為是不可忍受的塔嬉。
??
??
Fig. 10. 從多項(xiàng)式復(fù)雜度到指數(shù)復(fù)雜度
2.2 實(shí)例: Subset
Fig. 11 實(shí)例：Subset問(wèn)題
- 這個(gè)問(wèn)題如果沒(méi)有其他約束條件玩徊，最優(yōu)的算法就是逐一枚舉所有可能的子集，再統(tǒng)計(jì)其中元素的和谨究。其復(fù)雜度為
- Subset問(wèn)題是一個(gè)NP-complete問(wèn)題恩袱。
三、算法分析
??兩個(gè)主要任務(wù): 正確性 + 復(fù)雜度胶哲。
Fig. 12 算法分析：前提與方法
3.1 級(jí)數(shù)
- 算數(shù)級(jí)數(shù):
- 冪方級(jí)數(shù):
# 比冪次高一級(jí)
- 幾何級(jí)數(shù):
常用: - 收斂級(jí)數(shù)
- 其他常見(jiàn)級(jí)數(shù):
①調(diào)和級(jí)數(shù)
②對(duì)數(shù)級(jí)數(shù):
3.1 循環(huán) vs. 級(jí)數(shù)
- 二重循環(huán)：
①兩個(gè)控制變量之間沒(méi)有耦合: 復(fù)雜度為
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
O(1)_Operation(i, j)
②兩個(gè)控制變量之間存在耦合: 復(fù)雜度也是
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
O(1)_Operation(i, j)
Fig. 13 二重循環(huán)復(fù)雜度
③注意下面的循環(huán)復(fù)雜度為
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j+=j)
O(1)_Operation(i, j)
3.2 實(shí)例：非極端排序
- 問(wèn)題：給定整數(shù)子集S畔塔，|S| = n>=3，找出元素a，確保a既不是S的最大值也不是最小值澈吨。
- 解：只需要從S中任取三個(gè)元素把敢，然后找出這三個(gè)元素中的非極端元素即可。
-
說(shuō)明: 某些情況下無(wú)論問(wèn)題的規(guī)模多大谅辣，算法需要執(zhí)行的時(shí)間不變：
Fig. 14 非極端排序復(fù)雜度
3.3 實(shí)例：冒泡排序
Fig. 15 冒泡排序
vector<int> bubble_naive(vector<int> vec){
int steps=0;
int n = vec.size();
for (int i=0; i<n; ++i){
// No out of range error will be reported in cpp.
for (int j=0; j<n-1; ++j){
if (vec[j] > vec[j+1]){
swap(vec[j], vec[j+1]);
}
++steps;
}
}
cout<< "Steps: "<<steps<<endl;
return vec;
}
vector<int> bubble_optimized(vector<int> vec){
int steps=0;
int n = vec.size();
for (int i=n; i>0; --i){
for (int j=0; j<i-1; ++j){
if (vec[j] > vec[j+1]){
swap(vec[j], vec[j+1]);
}
++steps;
}
}
cout<< "Steps: "<<steps<<endl;
return vec;
}
vector<int> bubble_optimized2(vector<int> vec){
int steps=0;
int n = vec.size();
for (int i=n; i>0; --i){
bool swapped = false;
for (int j=0; j<i-1; ++j){
if (vec[j] > vec[j+1]){
swap(vec[j], vec[j+1]);
swapped = true;
}
++steps;
}
if (!swapped){
cout<< "Break! Steps: "<<steps<<endl;
return vec;
}
}
cout<< "Steps: "<<steps<<endl;
return vec;
}
// =======================
void main(){
//vector<int> vec = {1,4,2,3,5,8,9,7,0};
vector<int> vec = {1,2,4,3,5,6,7,8,9,22,0,11,12,3};
print(vec);
cout<<endl;
auto vec1=bubble_naive(vec);
auto vec2=bubble_optimized(vec);
auto vec3=bubble_optimized2(vec);
print(vec1);
print(vec2);
print(vec3);
}
- Output:
Steps: 182
Steps: 91
Break! Steps: 88
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 22,
四修赞、迭代與遞推
4.1 減而治之
??所謂“減而治之”，就是講一個(gè)復(fù)雜的問(wèn)題劃分成兩部分桑阶，其中一部分是
Fig. 16 減而治之
4.2 Max2問(wèn)題
Fig. 16 迭代解法一
-
迭代解法二：初始化兩個(gè)指針（下標(biāo)索引）并確定其順序柏副。從第三個(gè)元素開(kāi)始掃描，每次掃描先將當(dāng)前下標(biāo)元素和x2位置數(shù)值（較小的元素）進(jìn)行比較联逻，若大于x2搓扯，則x2的下標(biāo)更新為當(dāng)前下標(biāo)，同時(shí)和x1進(jìn)行比較包归。
Fig. 17. 迭代解法二 - 迭代解法二的最好情況需要n-1次比較锨推；最壞情況需要2n-3次比較，并沒(méi)有實(shí)質(zhì)性的改善公壤。
-
這個(gè)算法體現(xiàn)出分而治之思想的優(yōu)點(diǎn)换可。下面使用二分法，每次將數(shù)組均分成兩段厦幅，分別找出第一段(L)的max2元素X1L, X2L和第二段(R)的max2元素X1R, X2R沾鳄，然后操作為：將X1L于X1R進(jìn)行比較確定全局最大值（如X1L > X1R），那么再將X2L和X1R進(jìn)行比較確定次大值确憨。
Fig. 18 二分遞歸
#include<iostream>
#include<vector>
using namespace std;
//vector A: [lo, lo+1, lo+2, ..., hi)
void max2(vector<int> A, int lo, int hi, int &x1, int& x2){
if (hi - lo == 3) {
if (A[lo] < A[lo+1]){
if (A[lo+1]<A[lo+2]) {
x1=lo+2;
x2=A[lo+1]>A[lo]?lo+1:lo;
} else {
x1=lo+1;
x2=A[lo+2]>A[lo]?lo+2:lo;};
}
else { // lo > lo+1
if (A[lo]>A[lo+2]) {
x1=lo;
x2=A[lo+1]>A[lo+2] ? lo+1:lo+2;
} else {
x1=lo+2;x2=A[lo+1]>A[lo]?lo+1:lo;
}
}
return;
} //T(3)<=3;
if (hi - lo == 2) {
if (A[lo]>A[hi-1]){
x1 = lo;
x2 = hi-1;
} else {
x1 = hi-1;
x2 = lo;
}
return;
}
int mi = (lo + hi) / 2;
int X1L, X2L; max2(A, lo, mi, X1L, X2L);
int X1R, X2R; max2(A, mi, hi, X1R, X2R);
if (A[X1L] > A[X1R]){
x1 = X1L;
x2 = A[X2L] > A[X1R] ? X2L : X1R;
}
else{
x1 = X1R;
x2 = A[X2R] > A[X1L] ? X2R : X1L;
}
}
int main(){
vector<int> A={1,3,4,0,9,-2,8,11};
//vector<int> A={5,6};
int lo = 0;
int hi = A.size();
int x1, x2;
max2(A, lo, hi, x1, x2);
cout<<"Max 2 number: "<< A[x1]<<", "<<A[x2]<<endl;
}
龍哥系統(tǒng)組常用面試題目：
- 連續(xù)子數(shù)組的和 （動(dòng)態(tài)規(guī)劃）
- 二維數(shù)組向右或者向下走译荞，選擇和最大的路徑 （動(dòng)態(tài)規(guī)劃）
- 立方體八個(gè)頂點(diǎn)，一個(gè)點(diǎn)給一個(gè)數(shù)休弃，問(wèn)能否實(shí)現(xiàn)每個(gè)面四個(gè)頂點(diǎn)和相等 (動(dòng)態(tài)規(guī)劃/全排列吞歼，了解下)
- 求一個(gè)數(shù)組中最大的K個(gè)數(shù) （堆排序 /c++ map 平衡二叉樹(shù)）
- 背包問(wèn)題
- 長(zhǎng)度為n-1的數(shù)組中存放了1-n之間的n-1個(gè)數(shù)。找到缺失的數(shù)
- 二維數(shù)組從左往右從上往下遞增塔猾，判斷給定的數(shù)是否在數(shù)組中篙骡，若在則返回位置 （時(shí)間復(fù)雜度要求M+N）
- 找出鏈表中環(huán)的位置/鏈表的刪除和插入
- 字符串處理: 將字符串中的某個(gè)字符替換為指定字符串（不含目標(biāo)字符）
