算法應(yīng)用工程師考試題
三尺優(yōu)姬
mimi若聞
算法是比較復(fù)雜又基礎(chǔ)的學(xué)科，每個(gè)學(xué)編程的人都會(huì)學(xué)習(xí)大量的算法。而根據(jù)統(tǒng)計(jì)，以下這18個(gè)問題是面試中最容易遇到的，本文給出了一些基本答案，供算法方向工程師或?qū)Υ烁信d趣的程序員參考。1)請簡單解釋算法是什么?算法是一個(gè)定義良好的計(jì)算過程，它將一些值作為輸入并產(chǎn)生相應(yīng)的輸出值。簡單來說，它是將輸入轉(zhuǎn)換為輸出的一系列計(jì)算步驟。2)解釋什么是快速排序算法?快速排序算法能夠快速排序列表或查詢。它基于分割交換排序的原則，這種類型的算法占用空間較小，它將待排序列表分為三個(gè)主要部分：·小于Pivot的元素·樞軸元素Pivot(選定的比較值)·大于Pivot的元素3)解釋算法的時(shí)間復(fù)雜度?算法的時(shí)間復(fù)雜度表示程序運(yùn)行完成所需的總時(shí)間，它通常用大O表示法來表示。4)請問用于時(shí)間復(fù)雜度的符號類型是什么?用于時(shí)間復(fù)雜度的符號類型包括：·Big Oh：它表示小于或等于目標(biāo)多項(xiàng)式·Big Omega：它表示大于或等于目標(biāo)多項(xiàng)式·Big Theta：它表示與目標(biāo)多項(xiàng)式相等·Little Oh：它表示小于目標(biāo)多項(xiàng)式·Little Omega：它表示大于目標(biāo)多項(xiàng)式5)解釋二分法檢索如何工作?在二分法檢索中，我們先確定數(shù)組的中間位置，然后將要查找的值與數(shù)組中間位置的值進(jìn)行比較，若小于數(shù)組中間值，則要查找的值應(yīng)位于該中間值之前，依此類推，不斷縮小查找范圍，直至得到最終結(jié)果。6)解釋是否可以使用二分法檢索鏈表?由于隨機(jī)訪問在鏈表中是不可接受的，所以不可能到達(dá)O(1)時(shí)間的中間元素。因此，對于鏈表來說，二分法檢索是不可以的(對順序鏈表或排序后的鏈表是可以用的)。7)解釋什么是堆排序?堆排序可以看成是選擇排序的改進(jìn)，它可以定義為基于比較的排序算法。它將其輸入劃分為未排序和排序的區(qū)域，通過不斷消除最小元素并將其移動(dòng)到排序區(qū)域來收縮未排序區(qū)域。8)說明什么是Skip list?Skip list數(shù)據(jù)結(jié)構(gòu)化的方法，它允許算法在符號表或字典中搜索、刪除和插入元素。在Skip list中，每個(gè)元素由一個(gè)節(jié)點(diǎn)表示。搜索函數(shù)返回與key相關(guān)的值的內(nèi)容。插入操作將指定的鍵與新值相關(guān)聯(lián)，刪除操作可刪除指定的鍵。9)解釋插入排序算法的空間復(fù)雜度是多少?插入排序是一種就地排序算法，這意味著它不需要額外的或僅需要少量的存儲(chǔ)空間。對于插入排序，它只需要將單個(gè)列表元素存儲(chǔ)在初始數(shù)據(jù)的外側(cè)，從而使空間復(fù)雜度為O(1)。10)解釋什么是“哈希算法”，它們用于什么?“哈希算法”是一個(gè)哈希函數(shù)，它使用任意長度的字符串，并將其減少為唯一的固定長度字符串。它用于密碼有效性、消息和數(shù)據(jù)完整性以及許多其他加密系統(tǒng)。11)解釋如何查找鏈表是否有循環(huán)?要知道鏈表是否有循環(huán)，我們將采用兩個(gè)指針的方法。如果保留兩個(gè)指針，并且在處理兩個(gè)節(jié)點(diǎn)之后增加一個(gè)指針，并且在處理每個(gè)節(jié)點(diǎn)之后，遇到指針指向同一個(gè)節(jié)點(diǎn)的情況，這只有在鏈表有循環(huán)時(shí)才會(huì)發(fā)生。12)解釋加密算法的工作原理?加密是將明文轉(zhuǎn)換為稱為“密文”的密碼格式的過程。要轉(zhuǎn)換文本，算法使用一系列被稱為“鍵”的位來進(jìn)行計(jì)算。密鑰越大，創(chuàng)建密文的潛在模式數(shù)越多。大多數(shù)加密算法使用長度約為64到128位的固定輸入塊，而有些則使用流方法。13)列出一些常用的加密算法?一些常用的加密算法是：·3-way·Blowfish·CAST·CMEA·GOST·DES 和Triple DES·IDEA·LOKI等等14)解釋一個(gè)算法的最佳情況和最壞情況之間有什么區(qū)別?·最佳情況：算法的最佳情況解釋為算法執(zhí)行最佳的數(shù)據(jù)排列。例如，我們進(jìn)行二分法檢索，如果目標(biāo)值位于正在搜索的數(shù)據(jù)中心，則這就是最佳情況，最佳情況時(shí)間復(fù)雜度為0?！ぷ畈钋闆r：給定算法的最差輸入?yún)⒖?。例如快速排序，如果選擇關(guān)鍵值的子列表的最大或最小元素，則會(huì)導(dǎo)致最差情況出現(xiàn)，這將導(dǎo)致時(shí)間復(fù)雜度快速退化到O(n2)。15)解釋什么是基數(shù)排序算法?基數(shù)排序又稱“桶子法”，是通過比較數(shù)字將其分配到不同的“桶里”來排序元素的。它是線性排序算法之一。16)解釋什么是遞歸算法?遞歸算法是一個(gè)解決復(fù)雜問題的方法，將問題分解成較小的子問題，直到分解的足夠小，可以輕松解決問題為止。通常，它涉及一個(gè)調(diào)用自身的函數(shù)。17)提到遞歸算法的三個(gè)定律是什么?所有遞歸算法必須遵循三個(gè)規(guī)律：·遞歸算法必須有一個(gè)基點(diǎn)·遞歸算法必須有一個(gè)趨向基點(diǎn)的狀態(tài)變化過程·遞歸算法必須自我調(diào)用18)解釋什么是冒泡排序算法?冒泡排序算法也稱為下沉排序。在這種類型的排序中，要排序的列表的相鄰元素之間互相比較。如果它們按順序排列錯(cuò)誤，將交換值并以正確的順序排列，直到最終結(jié)果“浮”出水面。滿意記得采納哈
yy瘦胖紙
上采樣upsampling的主要目的是放大圖像，幾乎都是采用內(nèi)插值法，即在原有圖像像素的基礎(chǔ)上，在像素點(diǎn)值之間采用合適的插值算法插入新的元素。 線性插值法是指使用連接兩個(gè)已知量的直線來確定在這個(gè)兩個(gè)已知量之間的一個(gè)未知量的值的方法。 假設(shè)已知兩個(gè)坐標(biāo)(x0,y0)和(x1,y1)，要得到[x0,x1]區(qū)間內(nèi)某一位置x在直線上的值。 該直線的方程可表示為： 這樣 雙線性插值是插值算法中的一種，是線性插值的擴(kuò)展。利用原圖像中目標(biāo)點(diǎn)四周的四個(gè)真實(shí)存在的像素值來共同決定目標(biāo)圖中的一個(gè)像素值，其核心思想是在兩個(gè)方向分別進(jìn)行一次線性插值。 已知的紅色數(shù)據(jù)點(diǎn)和待插值的綠色數(shù)據(jù)點(diǎn) 假如我們想得到未知函數(shù)f在點(diǎn)P= (x,y) 的值，假設(shè)我們已知函數(shù)f在 四個(gè)點(diǎn)的值。 在x與y方向上，z值成單調(diào)性特性的應(yīng)用中，此種方法可以做外插運(yùn)算，即可以求解Q11~Q22所構(gòu)成的正方形以外的點(diǎn)的值。 總結(jié)：線性插值法利用原圖像中兩個(gè)點(diǎn)計(jì)算像素值進(jìn)行插值，雙線性插值法利用原圖像中四個(gè)點(diǎn)計(jì)算目標(biāo)像素值進(jìn)行插值。 這是最簡單的一種插值方法，不需要計(jì)算，在待求象素的四鄰象素中，將距離待求象素最近的鄰象素灰度賦給待求象素。設(shè)i+u, j+v(i, j為正整數(shù)， u, v為大于零小于1的小數(shù)，下同)為待求象素坐標(biāo)，則待求象素灰度的值 f(i+u, j+v)如下圖所示： 如果(i+u, j+v)落在A區(qū)，即u<, v<，則將左上角象素的灰度值賦給待求象素，同理，落在B區(qū)則賦予右上角的象素灰度值，落在C區(qū)則賦予左下角象素的灰度值，落在D區(qū)則賦予右下角象素的灰度值。 最鄰近元法計(jì)算量較小，但可能會(huì)造成插值生成的圖像灰度上的不連續(xù)，在灰度變化的地方可能出現(xiàn)明顯的鋸齒狀。 雙線性內(nèi)插法是利用待求象素四個(gè)鄰象素的灰度在兩個(gè)方向上作線性內(nèi)插。 如下圖所示： 對于 (i, j+v)，f(i, j) 到 f(i, j+1) 的灰度變化為線性關(guān)系，則有： f(i, j+v) = [f(i, j+1) - f(i, j)] * v + f(i, j) 同理對于 (i+1, j+v) 則有： f(i+1, j+v) = [f(i+1, j+1) - f(i+1, j)] * v + f(i+1, j) 從f(i, j+v) 到 f(i+1, j+v) 的灰度變化也為線性關(guān)系，由此可推導(dǎo)出待求象素灰度的計(jì)算式如下： f(i+u, j+v) = (1-u) * (1-v) * f(i, j) + (1-u) * v * f(i, j+1) + u * (1-v) * f(i+1, j) + u * v * f(i+1, j+1) 雙線性內(nèi)插法的計(jì)算比最鄰近點(diǎn)法復(fù)雜，計(jì)算量較大，但沒有灰度不連續(xù)的缺點(diǎn)，結(jié)果基本令人滿意。它具有低通濾波性質(zhì)，使高頻分量受損，圖像輪廓可能會(huì)有一點(diǎn)模糊。 該方法利用三次多項(xiàng)式S(x)求逼近理論上最佳插值函數(shù)sin(x)/x, 其數(shù)學(xué)表達(dá)式為： 待求像素(x, y)的灰度值由其周圍16個(gè)灰度值加權(quán)內(nèi)插得到，如下圖： 待求像素的灰度計(jì)算式如下： f(x, y) = f(i+u, j+v) = ABC 其中: 三次曲線插值方法計(jì)算量較大，但插值后的圖像效果最好。
優(yōu)質(zhì)工程師考試問答知識庫
