算法工程師面試題

1、.1、 算法工程師定義算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟?；蛘呖闯砂凑找笤O(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類問題。一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：1、有窮性： 一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；2、確切性： 算法的每一步驟必須有確切的定義；3、

2、輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件；4、輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；5、可行性： 算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。計(jì)算機(jī)科學(xué)家尼克勞斯-沃思曾著過一本著名的書數(shù)據(jù)結(jié)構(gòu)十算法= 程序，可見算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。編輯本段算法的復(fù)雜度同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指

3、算法需要消耗的時(shí)間資源。一般來說，計(jì)算機(jī)算法是問題規(guī)模n 的函數(shù)f(n)，算法的時(shí)間復(fù)雜度也因此記做T(n)=(f(n)因此，問題的規(guī)模n 越大，算法執(zhí)行的時(shí)間的增長率與f(n) 的增長率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Time Complexity）?？臻g復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。詳見百度百科詞條算法復(fù)雜度編輯本段算法設(shè)計(jì)與分析的基本方法1.遞推法遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關(guān)

4、系，從而達(dá)到目的，此方法稱為遞推法。2.遞歸遞歸指的是一個(gè)過程：函數(shù)不斷引用自身，直到引用的對(duì)象已知3.窮舉搜索法窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問題的解。4.貪婪法貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。5.分治法把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題

5、的解的合并。6.動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。7.迭代法迭代是數(shù)值分析中通過從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。編輯本段算法分類算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計(jì)算幾何的算法、圖論的算法、動(dòng)態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法。算法可以宏泛的分

6、為三類：有限的，確定性算法 這類算法在有限的一段時(shí)間內(nèi)終止。他們可能要花很長時(shí)間來執(zhí)行指定的任務(wù)，但仍將在一定的時(shí)間內(nèi)終止。這類算法得出的結(jié)果常取決于輸入值。有限的，非確定算法 這類算法在有限的時(shí)間內(nèi)終止。然而，對(duì)于一個(gè)（或一些）給定的數(shù)值，算法的結(jié)果并不是唯一的或確定的。無限的算法 是那些由于沒有定義終止定義條件，或定義的條件無法由輸入的數(shù)據(jù)滿足而不終止運(yùn)行的算法。通常，無限算法的產(chǎn)生是由于未能確定的定義終止條件。編輯本段舉例經(jīng)典的算法有很多，如：歐幾里德算法，割圓術(shù)，秦九韶算法。編輯本段算法經(jīng)典專著目前市面上有許多論述算法的書籍，其中最著名的便是計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（The Art Of C

7、omputer Programming) 以及算法導(dǎo)論（Introduction To Algorithms）。編輯本段算法的歷史“算法”即演算法的大陸中文名稱出自周髀算經(jīng)；而英文名稱Algorithm 來自于9世紀(jì)波斯數(shù)學(xué)家al-Khwarizmi，因?yàn)閍l-Khwarizmi在數(shù)學(xué)上提出了算法這個(gè)概念?！八惴ā痹瓰閍lgorism，意思是阿拉伯?dāng)?shù)字的運(yùn)算法則，在18世紀(jì)演變?yōu)閍lgorithm。歐幾里得算法被人們認(rèn)為是史上第一個(gè)算法。 第一次編寫程序是Ada Byron于1842年為巴貝奇分析機(jī)編寫求解解伯努利方程的程序，因此Ada Byron被大多數(shù)人認(rèn)為是世界上第一位程序員。因?yàn)椴闋査?/p>

8、巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機(jī)，這個(gè)算法未能在巴貝奇分析機(jī)上執(zhí)行。 因?yàn)閣ell-defined procedure缺少數(shù)學(xué)上精確的定義，19世紀(jì)和20世紀(jì)早期的數(shù)學(xué)家、邏輯學(xué)家在定義算法上出現(xiàn)了困難。20世紀(jì)的英國數(shù)學(xué)家圖靈提出了著名的圖靈論題，并提出一種假想的計(jì)算機(jī)的抽象模型，這個(gè)模型被稱為圖靈機(jī)。圖靈機(jī)的出現(xiàn)解決了算法定義的難題，圖靈的思想對(duì)算法的發(fā)展起到了重要作用的。=相關(guān)知識(shí)介紹（所有定義只為幫助讀者理解相關(guān)概念，并非嚴(yán)格定義）：1、穩(wěn)定排序和非穩(wěn)定排序簡單地說就是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們在排序之前的相對(duì)次序，我們就說這種排序方法

9、是穩(wěn)定的。反之，就是非穩(wěn)定的。比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過某種排序后為a1,a2,a4,a3,a5，則我們說這種排序是穩(wěn)定的，因?yàn)閍2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。2、內(nèi)排序和外排序在排序過程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱為內(nèi)排序；在排序過程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱為外排序。3、算法的時(shí)間復(fù)雜度和空間復(fù)雜度所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的

10、內(nèi)存空間。=功能：選擇排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)=算法思想簡單描述：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。選擇排序是不穩(wěn)定的。算法復(fù)雜度O(n2)-n的平方=*/void select_sort(int *x, int n)int i, j, min, t;for (i=0; in-1; i+)/*要選擇的次數(shù)：0n-2共n-1次*/min = i;/*假設(shè)當(dāng)前下標(biāo)為i的數(shù)最小，比較后再調(diào)整*/for (j=i+1; jn; j+)/*循環(huán)找出最小的數(shù)的

11、下標(biāo)是哪個(gè)*/if (*(x+j) =2 個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)-n的平方=*/void insert_sort(int *x, int n)int i, j, t;for (i=1; i=0 & t0; h=k)/*循環(huán)到?jīng)]有比較范圍*/for (j=0, k=0; j *(x+j+1)/*大的放在后面，小的放到前面*/t = *(x+j);*(x+j) = *(x+j+1);*(x+j+1) = t;/*完成交換*/k = j;/*保存最后下沉的位置

12、。這樣k后面的都是排序排好了的。*/=功能：希爾排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)=算法思想簡單描述：在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對(duì)插入下一個(gè)數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。下

13、面的函數(shù)是一個(gè)希爾排序算法的一個(gè)實(shí)現(xiàn)，初次取序列的一半為增量，以后每次減半，直到增量為1。希爾排序是不穩(wěn)定的。void shell_sort(int *x, int n)int h, j, k, t;for (h=n/2; h0; h=h/2)/*控制增量*/for (j=h; j=0 & t*(x+k); k-=h)*(x+k+h) = *(x+k);*(x+k+h) = t;=功能：快速排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中起止元素的下標(biāo)=算法思想簡單描述：快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能

14、確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少1?？焖倥判蛲ㄟ^一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。它是由C.A.R.Hoare于1962年提出的。顯然快速排序可以用遞歸實(shí)現(xiàn)，當(dāng)然也可以用?；膺f歸實(shí)現(xiàn)。下面的函數(shù)是用遞歸實(shí)現(xiàn)的，有興趣的朋友可以改成非遞歸的?？焖倥判蚴遣环€(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n2)=*/void quick_sort(int *x, int low, int high)int i, j, t;if (low hig

15、h)/*要排序的元素起止下標(biāo)，保證小的放在左邊，大的放在右邊。這里以下標(biāo)為low的元素為基準(zhǔn)點(diǎn)*/i = low;j = high;t = *(x+low);/*暫存基準(zhǔn)點(diǎn)的數(shù)*/while (ij)/*循環(huán)掃描*/while (it)/*在右邊的只要比基準(zhǔn)點(diǎn)大仍放在右邊*/j-;/*前移一個(gè)位置*/if (ij)*(x+i) = *(x+j);/*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)小的數(shù)，替換基準(zhǔn)點(diǎn)的數(shù)*/i+;/*后移一個(gè)位置，并以此為基準(zhǔn)點(diǎn)*/while (ij & *(x+i)=t)/*在左邊的只要小于等于基準(zhǔn)點(diǎn)仍放在左邊*/i+;/*后移一個(gè)位置*/if (i=h2i,hi=2i+1）或

16、（hi=h2i,hi=2i+1）(i=1,2,.,n/2)時(shí)稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹、右子樹。初始時(shí)把要排序的數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹，調(diào)整它們的存儲(chǔ)順序，使之成為一個(gè)堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。然后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。然后對(duì)前面(n-1)個(gè)數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。從算法描述來看，堆排序需要兩個(gè)過程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組

17、成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度O(nlog2n)。=功能：滲透建堆輸入：數(shù)組名稱（也就是數(shù)組首地址）、參與建堆元素的個(gè)數(shù)、從第幾個(gè)元素開始*/void sift(int *x, int n, int s)int t, k, j;t = *(x+s);/*暫存開始元素*/k = s;/*開始元素下標(biāo)*/j = 2*k + 1;/*右子樹元素下標(biāo)*/while (jn)if (jn-1 & *(x+j) *(x+j+1)/*判斷是否滿足堆的條件：滿足就繼續(xù)下一輪比較，否則調(diào)整。*/j+;if (t=0; i-)sift(x,n,i);/*初始建堆*/for (k=n-1; k=1; k-)t = *(x+0);/*堆頂放到最后*/*(x+0) = *(x+k);*(x+k) = t;sift(x,k,0);/*剩下的數(shù)再建堆*/void main()#define MAX 4int *p, i, aMAX;/*錄入測試數(shù)據(jù)*/p = a;printf(Input %d number for sorting :n,MAX);for (i=0; iMAX;