資訊專欄INFORMATION COLUMN
摘要：動態(tài)規(guī)劃背包士兵路徑復(fù)雜度談算法一定要考慮復(fù)雜度時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度計(jì)算機(jī)基本操作的次數(shù)匯編指令的條數(shù)尋址跳轉(zhuǎn)空間復(fù)雜度所需占用的內(nèi)存字節(jié)數(shù)兩者區(qū)別空間是可以返回利用的。
面試求職班一筆記
算法主要研究：時空復(fù)雜度
算法的特征：
有窮性，
確定性，
可行性，
可能沒有輸入，但一定有輸出
常用算法
窮舉法（eg：求N個數(shù)的全排列；8皇后問題）
減而治之（二分查找——減而治之；歸并排序——分而治之）
貪心算法（最小生成樹；單源最短路）所謂貪心算法是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。
動態(tài)規(guī)劃（背包；士兵路徑）
復(fù)雜度
談算法一定要考慮復(fù)雜度
時間復(fù)雜度和空間復(fù)雜度
時間復(fù)雜度：計(jì)算機(jī)基本操作的次數(shù)（匯編指令的條數(shù)）+ - * / % 尋址 跳轉(zhuǎn)
空間復(fù)雜度：所需占用的內(nèi)存字節(jié)數(shù)
兩者區(qū)別：空間是可以返回利用的。
表示方法：O(n) 忽略常數(shù)（高階無窮?。┳⒁猓核惴◤?fù)雜度是考慮算法最壞情況時的復(fù)雜度
eg: 快速排序的復(fù)雜度 O(n^2)，這個就是他的最壞情況
常見的復(fù)雜度
O(1): 基本運(yùn)算 + - * / % 尋址 跳轉(zhuǎn)
O(logN): 二分查找
O(N^(1/2)): 枚舉約數(shù)
O(N): 線性查找
O(N^2): 樸素最近帶你對
O(N^3): Floyd最短路；普通矩陣乘法
O(NlogN): 歸并排序；快速排序的期望復(fù)雜度；基于比較排序的算法下界
$$a_1,a_2,...a_n 排序全排列的時間復(fù)雜度為 n!$$
$$ 當(dāng) a_i< a_j時$$
$$復(fù)雜度變?yōu)? frac{n!}{2}$$
$$當(dāng)有k個關(guān)系時，每次都能排除一般的可能$$
$$復(fù)雜度為: frac{n!}{2^k}$$
$$令: frac{n!}{2^k} = 1 即 n!=2^k$$
$$k=log_{2}{n!} < log_{2}{n^n}=nlog_{2}{n}=nfrac{log n}{log2}< nlog{n}$$
以上為推導(dǎo)過程
8. O($2^N$): 枚舉全部的子集 注意：一個集合全部子集的數(shù)量是2^N
9. O($N!$): 枚舉全部排列
總結(jié):
優(yōu)秀算法排序：
$$O(1) < O(log{n}) < O(sqrt{n} < O(n) < O(nlog{n}))$$
可以優(yōu)化的：
$$O(n^2)< O(n^3)< O(2^n)< O(n!)$$
算法估計(jì)，計(jì)算機(jī)1s能運(yùn)算1億條指令，注意以下數(shù)字
$$(1000)^2=1億; (465)^3=100,544,625; 12!=479001600$$
常用的時間復(fù)雜度分析方法 1. 輸入輸出
1. N個數(shù)組求和，時間復(fù)雜度下限為: O(n)
2. 輸出全排列的復(fù)雜度在O(n!)以上
2. 循環(huán)次數(shù)
eg: 循環(huán)嵌套的復(fù)雜度至少是O(n^2)
for(i...n)
for(i...n)
3. 均攤分析法
多個操作一起計(jì)算時間復(fù)雜度
eg1: MULTIPOP的隊(duì)列，可以一次性出隊(duì)k個元素，但每個元素出入隊(duì)列只能有一次
eg2: 動態(tài)數(shù)據(jù)尾部插入操作（C++中是vector，java中是ArrayList）
一旦元素超過容量限制，則重新擴(kuò)大并分配空間，將舊數(shù)據(jù)復(fù)制到新的內(nèi)存地址上。
有空間的情況下復(fù)雜度是O(1)
空間滿了再擴(kuò)大的時候的復(fù)雜度是O(n)
重新分配k次的復(fù)雜度是O(2^n)
$$O(1)+O(2)+O(4)+...+O(2^n)=O(2^n-1)$$
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/71032.html
摘要：緩存算法我是，我會統(tǒng)計(jì)每一個緩存數(shù)據(jù)的使用頻率，我會把使用最少的緩存替換出緩存區(qū)。瀏覽器就是使用了我作為緩存算法。在緩存系統(tǒng)中找出最少最近的對象是需要較高的時空成本。再來一次機(jī)會的緩存算法，是對的優(yōu)化。直到新的緩存對象被放入。 緩存 什么是緩存？ showImg(https://segmentfault.com/img/bVusZg); 存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時地方，因?yàn)槿≡?..
摘要：學(xué)習(xí)筆記使用粒子系統(tǒng)模擬時空隧道本例的運(yùn)行結(jié)果如圖時空隧道演示地址的粒子系統(tǒng)的粒子系統(tǒng)主要是依靠精靈體來創(chuàng)建的，要實(shí)現(xiàn)中的粒子系統(tǒng)創(chuàng)建，一般有兩種方式。 WebGL three.js學(xué)習(xí)筆記 使用粒子系統(tǒng)模擬時空隧道 本例的運(yùn)行結(jié)果如圖：showImg(https://img-blog.csdnimg.cn/20190426222855492.png?x-oss-process=ima...
摘要：技術(shù)總言這次主要說最近發(fā)展的無監(jiān)督特征學(xué)習(xí)和深入學(xué)習(xí)，其對于時間序列模型問題的評價。建模連續(xù)數(shù)據(jù)的傳統(tǒng)方法包括從假定時間序列模型參數(shù)的估計(jì)，如自回歸模型和線性動力系統(tǒng)，和著名的隱馬爾可夫模型。此外，時間序列對時間變量有明顯依賴性。 技術(shù)總言：這次主要說最近發(fā)展的無監(jiān)督特征學(xué)習(xí)和深入學(xué)習(xí)，其對于時間序列模型問題的評價。這些技術(shù)已經(jīng)展現(xiàn)了希望對于建模靜態(tài)數(shù)據(jù)，如計(jì)算機(jī)視覺，把它們應(yīng)用到時間序列數(shù)...
摘要：目錄一時間復(fù)雜度例題二空間復(fù)雜度例題三常見復(fù)雜度對比一時間復(fù)雜度時間復(fù)雜度一個算法所花費(fèi)的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)。找到某條基本語句與問題規(guī)模之間的數(shù)學(xué)表達(dá)式，就是算出了該算法的時間復(fù)雜度。 ...
閱讀 1701·2021-09-22 15:25
閱讀 1619·2021-09-07 10:06
閱讀 3254·2019-08-30 15:53
閱讀 1152·2019-08-29 13:12
閱讀 3458·2019-08-29 13:07
閱讀 803·2019-08-28 18:19
閱讀 2348·2019-08-27 10:57
閱讀 1042·2019-08-26 13:29
