臨迫性演算法

A. 演算法空間復雜度怎麼算

演算法空間復雜度計算方法：

一個演算法的空間復雜度只考慮在運行過程中為局部變數分配的存儲空間的大小，它包括為參數表中形參變數分配的存儲空間和為在函數體中定義的局部變數分配的存儲空間兩個部分。

若一個演算法為遞歸演算法，其空間復雜度為遞歸所使用的堆棧空間的大小，它等於一次調用所分配的臨時存儲空間的大小乘以被調用的次數(即為遞歸調用的次數加1，這個1表示開始進行的一次非遞歸調用)。

演算法的空間復雜度一般也以數量級的形式給出。如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為O(log2n)；當一個演算法的空間復雜度與n成線性比例關系時，可表示為O(n)。若形參為數組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應實參變數的地址，以便由系統自動引用實參變數。

(1)臨迫性演算法擴展閱讀：

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 。而一般的遞歸演算法就要有O(n)的空間復雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要佔用的存儲空間兩個方面衡量。

個演算法的空間復雜度S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。空間復雜度(SpaceComplexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。一個演算法在計算機存儲器上所佔用的存儲空間，包括存儲演算法本身所佔用的存儲空間，演算法的輸入輸出數據所佔用的存儲空間和演算法在運行過程中臨時佔用的存儲空間這三個方面。

B. 什麼是非搶占優先演算法

理論：
為照顧緊迫性作業，使之在進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。它分為兩種：
（一）非搶占式優先權演算法；
（二）搶占式優先權調度演算法。
1.非搶占式優先權演算法：系統一旦把處理機分配給就緒隊列中優先權最高的進程後,該進程便一直執行下去,直至完成。

2.搶占式優先權調度演算法：系統同樣把處理機分配給優先權最高的進程,使之執行.但在其執行期間,只要又出現了另一個其優先權更高的進程,進程調度程序就立即停止當前進程(原優先權最高的進程)的執行,重新將處理機分配給新到的優先權最高的進程。

分析：
採用非搶占式優先演算法時，最先來到的是進程P1，所以最先處理進程P1直到它結束，用時10；
在這10時間內進程P2先到來，然後是P3、P4，最後是P5，由於這些進程不能搶佔P1的進程，所以只能等待P1完成。
這些等待進程中P4的優先數最高，所以當P1執行完成後，先執行進程P4。
依次類推，最後可得作業順序為：P1=>P4=>P3=>P5=>P2

C. 什麼是PLP演算法

Proceral Language Processor, 過程語言處理程序

D. 機器學習新手必看十大演算法

機器學習新手必看十大演算法
本文介紹了機器學習新手需要了解的 10 大演算法，包括線性回歸、Logistic 回歸、樸素貝葉斯、K 近鄰演算法等。
在機器學習中，有一種叫做「沒有免費的午餐」的定理。簡而言之，它指出沒有任何一種演算法對所有問題都有效，在監督學習(即預測建模)中尤其如此。
例如，你不能說神經網路總是比決策樹好，反之亦然。有很多因素在起作用，例如數據集的大小和結構。
因此，你應該針對具體問題嘗試多種不同演算法，並留出一個數據「測試集」來評估性能、選出優勝者。
當然，你嘗試的演算法必須適合你的問題，也就是選擇正確的機器學習任務。打個比方，如果你需要打掃房子，你可能會用吸塵器、掃帚或拖把，但是你不會拿出鏟子開始挖土。
大原則
不過也有一個普遍原則，即所有監督機器學習演算法預測建模的基礎。
機器學習演算法被描述為學習一個目標函數 f，該函數將輸入變數 X 最好地映射到輸出變數 Y：Y = f(X)
這是一個普遍的學習任務，我們可以根據輸入變數 X 的新樣本對 Y 進行預測。我們不知道函數 f 的樣子或形式。如果我們知道的話，我們將會直接使用它，不需要用機器學習演算法從數據中學習。
最常見的機器學習演算法是學習映射 Y = f(X) 來預測新 X 的 Y。這叫做預測建模或預測分析，我們的目標是盡可能作出最准確的預測。
對於想了解機器學習基礎知識的新手，本文將概述數據科學家使用的 top 10 機器學習演算法。
1. 線性回歸
線性回歸可能是統計學和機器學習中最知名和最易理解的演算法之一。
預測建模主要關注最小化模型誤差或者盡可能作出最准確的預測，以可解釋性為代價。我們將借用、重用包括統計學在內的很多不同領域的演算法，並將其用於這些目的。
線性回歸的表示是一個方程，它通過找到輸入變數的特定權重(稱為系數 B)，來描述一條最適合表示輸入變數 x 與輸出變數 y 關系的直線。
線性回歸
例如：y = B0 + B1 * x
我們將根據輸入 x 預測 y，線性回歸學習演算法的目標是找到系數 B0 和 B1 的值。
可以使用不同的技術從數據中學習線性回歸模型，例如用於普通最小二乘法和梯度下降優化的線性代數解。
線性回歸已經存在了 200 多年，並得到了廣泛研究。使用這種技術的一些經驗是盡可能去除非常相似(相關)的變數，並去除噪音。這是一種快速、簡單的技術，可以首先嘗試一下。
2. Logistic 回歸
Logistic 回歸是機器學習從統計學中借鑒的另一種技術。它是解決二分類問題的首選方法。
Logistic 回歸與線性回歸相似，目標都是找到每個輸入變數的權重，即系數值。與線性回歸不同的是，Logistic 回歸對輸出的預測使用被稱為 logistic 函數的非線性函數進行變換。
logistic 函數看起來像一個大的 S，並且可以將任何值轉換到 0 到 1 的區間內。這非常實用，因為我們可以規定 logistic 函數的輸出值是 0 和 1(例如，輸入小於 0.5 則輸出為 1)並預測類別值。
Logistic 回歸
由於模型的學習方式，Logistic 回歸的預測也可以作為給定數據實例(屬於類別 0 或 1)的概率。這對於需要為預測提供更多依據的問題很有用。
像線性回歸一樣，Logistic 回歸在刪除與輸出變數無關的屬性以及非常相似(相關)的屬性時效果更好。它是一個快速的學習模型，並且對於二分類問題非常有效。
3. 線性判別分析(LDA)
Logistic 回歸是一種分類演算法，傳統上，它僅限於只有兩類的分類問題。如果你有兩個以上的類別，那麼線性判別分析是首選的線性分類技術。
LDA 的表示非常簡單直接。它由數據的統計屬性構成，對每個類別進行計算。單個輸入變數的 LDA 包括：
每個類別的平均值;
所有類別的方差。
線性判別分析
進行預測的方法是計算每個類別的判別值並對具備最大值的類別進行預測。該技術假設數據呈高斯分布(鍾形曲線)，因此最好預先從數據中刪除異常值。這是處理分類預測建模問題的一種簡單而強大的方法。
4. 分類與回歸樹
決策樹是預測建模機器學習的一種重要演算法。
決策樹模型的表示是一個二叉樹。這是演算法和數據結構中的二叉樹，沒什麼特別的。每個節點代表一個單獨的輸入變數 x 和該變數上的一個分割點(假設變數是數字)。
決策樹
決策樹的葉節點包含一個用於預測的輸出變數 y。通過遍歷該樹的分割點，直到到達一個葉節點並輸出該節點的類別值就可以作出預測。
決策樹學習速度和預測速度都很快。它們還可以解決大量問題，並且不需要對數據做特別准備。
5. 樸素貝葉斯
樸素貝葉斯是一個簡單但是很強大的預測建模演算法。
該模型由兩種概率組成，這兩種概率都可以直接從訓練數據中計算出來：1)每個類別的概率;2)給定每個 x 的值，每個類別的條件概率。一旦計算出來，概率模型可用於使用貝葉斯定理對新數據進行預測。當你的數據是實值時，通常假設一個高斯分布(鍾形曲線)，這樣你可以簡單的估計這些概率。
貝葉斯定理
樸素貝葉斯之所以是樸素的，是因為它假設每個輸入變數是獨立的。這是一個強大的假設，真實的數據並非如此，但是，該技術在大量復雜問題上非常有用。
6. K 近鄰演算法
KNN 演算法非常簡單且有效。KNN 的模型表示是整個訓練數據集。是不是很簡單?
KNN 演算法在整個訓練集中搜索 K 個最相似實例(近鄰)並匯總這 K 個實例的輸出變數，以預測新數據點。對於回歸問題，這可能是平均輸出變數，對於分類問題，這可能是眾數(或最常見的)類別值。
訣竅在於如何確定數據實例間的相似性。如果屬性的度量單位相同(例如都是用英寸表示)，那麼最簡單的技術是使用歐幾里得距離，你可以根據每個輸入變數之間的差值直接計算出來其數值。
K 近鄰演算法
KNN 需要大量內存或空間來存儲所有數據，但是只有在需要預測時才執行計算(或學習)。你還可以隨時更新和管理訓練實例，以保持預測的准確性。
距離或緊密性的概念可能在非常高的維度(很多輸入變數)中會瓦解，這對演算法在你的問題上的性能產生負面影響。這被稱為維數災難。因此你最好只使用那些與預測輸出變數最相關的輸入變數。
7. 學習向量量化
K 近鄰演算法的一個缺點是你需要遍歷整個訓練數據集。學習向量量化演算法(簡稱 LVQ)是一種人工神經網路演算法，它允許你選擇訓練實例的數量，並精確地學習這些實例應該是什麼樣的。
學習向量量化
LVQ 的表示是碼本向量的集合。這些是在開始時隨機選擇的，並逐漸調整以在學習演算法的多次迭代中最好地總結訓練數據集。在學習之後，碼本向量可用於預測(類似 K 近鄰演算法)。最相似的近鄰(最佳匹配的碼本向量)通過計算每個碼本向量和新數據實例之間的距離找到。然後返回最佳匹配單元的類別值或(回歸中的實際值)作為預測。如果你重新調整數據，使其具有相同的范圍(比如 0 到 1 之間)，就可以獲得最佳結果。
如果你發現 KNN 在你的數據集上達到很好的結果，請嘗試用 LVQ 減少存儲整個訓練數據集的內存要求。
8. 支持向量機(SVM)
支持向量機可能是最受歡迎和最廣泛討論的機器學習演算法之一。
超平面是分割輸入變數空間的一條線。在 SVM 中，選擇一條可以最好地根據輸入變數類別(類別 0 或類別 1)對輸入變數空間進行分割的超平面。在二維中，你可以將其視為一條線，我們假設所有的輸入點都可以被這條線完全的分開。SVM 學習演算法找到了可以讓超平面對類別進行最佳分割的系數。
支持向量機
超平面和最近的數據點之間的距離被稱為間隔。分開兩個類別的最好的或最理想的超平面具備最大間隔。只有這些點與定義超平面和構建分類器有關。這些點被稱為支持向量，它們支持或定義了超平面。實際上，優化演算法用於尋找最大化間隔的系數的值。
SVM 可能是最強大的立即可用的分類器之一，值得一試。
9. Bagging 和隨機森林
隨機森林是最流行和最強大的機器學習演算法之一。它是 Bootstrap Aggregation(又稱 bagging)集成機器學習演算法的一種。
bootstrap 是從數據樣本中估算數量的一種強大的統計方法。例如平均數。你從數據中抽取大量樣本，計算平均值，然後平均所有的平均值以便更好的估計真實的平均值。
bagging 使用相同的方法，但是它估計整個統計模型，最常見的是決策樹。在訓練數據中抽取多個樣本，然後對每個數據樣本建模。當你需要對新數據進行預測時，每個模型都進行預測，並將所有的預測值平均以便更好的估計真實的輸出值。
隨機森林
隨機森林是對這種方法的一種調整，在隨機森林的方法中決策樹被創建以便於通過引入隨機性來進行次優分割，而不是選擇最佳分割點。
因此，針對每個數據樣本創建的模型將會與其他方式得到的有所不同，不過雖然方法獨特且不同，它們仍然是准確的。結合它們的預測可以更好的估計真實的輸出值。
如果你用方差較高的演算法(如決策樹)得到了很好的結果，那麼通常可以通過 bagging 該演算法來獲得更好的結果。
10. Boosting 和 AdaBoost
Boosting 是一種集成技術，它試圖集成一些弱分類器來創建一個強分類器。這通過從訓練數據中構建一個模型，然後創建第二個模型來嘗試糾正第一個模型的錯誤來完成。一直添加模型直到能夠完美預測訓練集，或添加的模型數量已經達到最大數量。
AdaBoost 是第一個為二分類開發的真正成功的 boosting 演算法。這是理解 boosting 的最佳起點。現代 boosting 方法建立在 AdaBoost 之上，最顯著的是隨機梯度提升。
AdaBoost
AdaBoost與短決策樹一起使用。在第一個決策樹創建之後，利用每個訓練實例上樹的性能來衡量下一個決策樹應該對每個訓練實例付出多少注意力。難以預測的訓練數據被分配更多權重，而容易預測的數據分配的權重較少。依次創建模型，每個模型在訓練實例上更新權重，影響序列中下一個決策樹的學習。在所有決策樹建立之後，對新數據進行預測，並且通過每個決策樹在訓練數據上的精確度評估其性能。
因為在糾正演算法錯誤上投入了太多注意力，所以具備已刪除異常值的干凈數據非常重要。
總結
初學者在面對各種機器學習演算法時經常問：「我應該用哪個演算法?」這個問題的答案取決於很多因素，包括：(1)數據的大小、質量和特性;(2)可用的計算時間;(3)任務的緊迫性;(4)你想用這些數據做什麼。
即使是經驗豐富的數據科學家在嘗試不同的演算法之前，也無法分辨哪種演算法會表現最好。雖然還有很多其他的機器學習演算法，但本篇文章中討論的是最受歡迎的演算法。如果你是機器學習的新手，這將是一個很好的學習起點。

E. 進程調度演算法

調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。
一、先來先服務和短作業（進程）優先調度演算法

1. 先來先服務調度演算法。先來先服務（FCFS）調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度， 也可用於進程調度。FCFS演算法比較有利於長作業（進程），而不利於短作業（進程）。由此可知，本演算法適合於CPU繁忙型作業， 而不利於I/O繁忙型的作業（進程）。
2. 短作業（進程）優先調度演算法。短作業（進程）優先調度演算法（SJ/PF）是指對短作業或短進程優先調度的演算法，該演算法既可用於作業調度， 也可用於進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

二、高優先權優先調度演算法

1. 優先權調度演算法的類型。為了照顧緊迫性作業，使之進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。 此演算法常被用在批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度，還可以用於實時系統中。當其用於作業調度， 將後備隊列中若干個優先權最高的作業裝入內存。當其用於進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該演算法分成以下兩種：
1)非搶占式優先權演算法
2)搶占式優先權調度演算法（高性能計算機操作系統）
2. 優先權類型 。對於最高優先權優先調度演算法，其核心在於：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。
3. 高響應比優先調度演算法
為了彌補短作業優先演算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間

三、基於時間片的輪轉調度演算法

1. 時間片輪轉法。時間片輪轉法一般用於進程調度，每次調度，把CPU分配隊首進程，並令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鍾中斷請求，該進程被停止，並被送往就緒隊列末尾；依次循環。 2. 多級反饋隊列調度演算法 多級反饋隊列調度演算法多級反饋隊列調度演算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度演算法。 其實施過程如下：
1) 設置多個就緒隊列，並為各個隊列賦予不同的優先順序。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。
2) 當一個新進程進入內存後，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最後隊列）後，便按第n隊列時間片輪轉運行。
3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1到第（i-1）隊列空時， 才會調度第i隊列中的進程運行，並執行相應的時間片輪轉。
4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，並把正在運行的進程放在第i隊列的隊尾。

F. 比較演算法優缺點：

作業調度演算法 .
1.先來先服務（FCFS, First Come First Serve）是最簡單的調度演算法，按先後順序進行調度。

定義：
按照作業提交或進程變為就緒狀態的先後次序，分派CPU；

當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。

在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或進程出讓CPU。

適用場景：
比較有利於長作業，而不利於短作業。因為長作業會長時間占據處理機。

有利於CPU繁忙的作業，而不利於I/O繁忙的作業。

演算法實現原理圖：

2. 輪轉法(Round Robin)
輪轉法是讓每個進程在就緒隊列中的等待時間與享受服務的時間成正比例。

定義：
將系統中所有的就緒進程按照FCFS原則，排成一個隊列。

每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。

在一個時間片結束時，發生時鍾中斷。

調度程序據此暫停當前進程的執行，將其送到就緒隊列的末尾，並通過上下文切換執行當前的隊首進程。

進程可以未使用完一個時間片，就出讓CPU（如阻塞）。

時間片長度的確定：
時間片長度變化的影響

過長－>退化為FCFS演算法，進程在一個時間片內都執行完，響應時間長。

過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，響應時間長。

對響應時間的要求：T(響應時間)=N(進程數目)*q(時間片)

就緒進程的數目：數目越多，時間片越小

系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使響應時間，平均周轉時間和平均帶權周轉時間延長。

演算法實現原理圖：

3. 多級反饋隊列演算法(Round Robin with Multiple Feedback)
多級反饋隊列演算法是輪轉演算法和優先順序演算法的綜合和發展。

定義：
設置多個就緒隊列，分別賦予不同的優先順序，如逐級降低，隊列1的優先順序最高。每個隊列執行時間片的長度也不同，規定優先順序越低則時間片越長，如逐級加倍。

新進程進入內存後，先投入隊列1的末尾，按FCFS演算法調度；若按隊列1一個時間片未能執行完，則降低投入到隊列2的末尾，同樣按FCFS演算法調度；如此下去，降低到最後的隊列，則按「時間片輪轉」演算法調度直到完成。

僅當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程執行。如果進程執行時有新進程進入較高優先順序的隊列，則搶先執行新進程，並把被搶先的進程投入原隊列的末尾。

優點：
為提高系統吞吐量和縮短平均周轉時間而照顧短進程。

為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程。

不必估計進程的執行時間，動態調節

幾點說明：
I/O型進程：讓其進入最高優先順序隊列，以及時響應I/O交互。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞隊列。

計算型進程：每次都執行完時間片，進入更低級隊列。最終採用最大時間片來執行，減少調度次數。

I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的隊列，以免每次都回到最高優先順序隊列後再逐次下降。

為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先順序；時間片用完時，降低優先順序。

演算法實現原理圖：

4. 優先順序法（Priority Scheling）
優先順序演算法是多級隊列演算法的改進，平衡各進程對響應時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。

靜態優先順序：
作業調度中的靜態優先順序大多按以下原則確定：

由用戶自己根據作業的緊急程度輸入一個適當的優先順序。

由系統或操作員根據作業類型指定優先順序。

系統根據作業要求資源情況確定優先順序。

進程的靜態優先順序的確定原則：

按進程的類型給予不同的優先順序。

將作業的情態優先順序作為它所屬進程的優先順序。

動態優先順序：
進程的動態優先順序一般根據以下原則確定：

根據進程佔用有CPU時間的長短來決定。

根據就緒進程等待CPU的時間長短來決定。

5．短作業優先法（SJF, Shortest Job First）
短作業優先又稱為「短進程優先」SPN(Shortest Process Next)；這是對FCFS演算法的改進，其目標是減少平均周轉時間。

定義：
對預計執行時間短的作業（進程）優先分派處理機。通常後來的短作業不搶先正在執行的作業。

SJF的特點：
(1) 優點：

比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間；

提高系統的吞吐量；

(2) 缺點：

對長作業非常不利，可能長時間得不到執行；

未能依據作業的緊迫程度來劃分執行的優先順序；

難以准確估計作業（進程）的執行時間，從而影響調度性能。

SJF的變型：
「最短剩餘時間優先」SRT(Shortest Remaining Time)（允許比當前進程剩餘時間更短的進程來搶占）

「最高響應比優先」HRRN(Highest Response Ratio Next)（響應比R = (等待時間 + 要求執行時間) / 要求執行時間，是FCFS和SJF的折衷）

6. 最高響應比優先法(HRN，Highest Response_ratio Next)
最高響應比優先法是對FCFS方式和SJF方式的一種綜合平衡。FCFS方式只考慮每個作業的等待時間而未考慮執行時間的長短，而SJF方式只考慮執行時間而未考慮等待時間的長短。因此，這兩種調度演算法在某些極端情況下會帶來某些不便。HRN調度策略同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。

響應比R定義如下： R =(W+T)/T = 1+W/T

其中T為該作業估計需要的執行時間，W為作業在後備狀態隊列中的等待時間。每當要進行作業調度時，系統計算每個作業的響應比，選擇其中R最大者投入執行。這樣，即使是長作業，隨著它等待時間的增加，W / T也就隨著增加，也就有機會獲得調度執行。這種演算法是介於FCFS和SJF之間的一種折中演算法。由於長作業也有機會投入運行，在同一時間內處理的作業數顯然要少於SJF法，從而採用HRN方式時其吞吐量將小於採用SJF 法時的吞吐量。另外，由於每次調度前要計算響應比，系統開銷也要相應增加。