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