算法學習筆記一、時空復雜度

wuyumin 發布于2019-08-16 11:08 / 1861人閱讀

摘要：動態規劃背包士兵路徑復雜度談算法一定要考慮復雜度時間復雜度和空間復雜度時間復雜度計算機基本操作的次數匯編指令的條數尋址跳轉空間復雜度所需占用的內存字節數兩者區別空間是可以返回利用的。

面試求職班一筆記

算法主要研究：時空復雜度

算法的特征：

有窮性，

確定性，

可行性，

可能沒有輸入，但一定有輸出

常用算法

窮舉法（eg：求N個數的全排列；8皇后問題）

減而治之（二分查找——減而治之；歸并排序——分而治之）

貪心算法（最小生成樹；單源最短路）所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

動態規劃（背包；士兵路徑）

復雜度

談算法一定要考慮復雜度

時間復雜度和空間復雜度

時間復雜度：計算機基本操作的次數（匯編指令的條數）+ - * / % 尋址跳轉

空間復雜度：所需占用的內存字節數

兩者區別：空間是可以返回利用的。

表示方法：O(n) 忽略常數（高階無窮小）注意：算法復雜度是考慮算法最壞情況時的復雜度

eg: 快速排序的復雜度 O(n^2)，這個就是他的最壞情況

常見的復雜度

O(1): 基本運算 + - * / % 尋址跳轉

O(logN): 二分查找

O(N^(1/2)): 枚舉約數

O(N): 線性查找

O(N^2): 樸素最近帶你對

O(N^3): Floyd最短路；普通矩陣乘法

O(NlogN): 歸并排序；快速排序的期望復雜度；基于比較排序的算法下界

$$a_1,a_2,...a_n 排序全排列的時間復雜度為 n!$$
$$ 當 a_i< a_j時$$
$$復雜度變為: 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$): 枚舉全部的子集   注意：一個集合全部子集的數量是2^N
        9. O($N!$): 枚舉全部排列

總結:

優秀算法排序：

$$O(1) < O(log{n}) < O(sqrt{n} < O(n) < O(nlog{n}))$$

可以優化的：

$$O(n^2)< O(n^3)< O(2^n)< O(n!)$$

算法估計，計算機1s能運算1億條指令，注意以下數字

$$(1000)^2=1億; (465)^3=100,544,625; 12!=479001600$$

常用的時間復雜度分析方法

    1. 輸入輸出
        1. N個數組求和，時間復雜度下限為: O(n)
        2. 輸出全排列的復雜度在O(n!)以上
    2. 循環次數
        eg: 循環嵌套的復雜度至少是O(n^2)
        for(i...n)
            for(i...n)
    
    3. 均攤分析法
        多個操作一起計算時間復雜度
        eg1: MULTIPOP的隊列，可以一次性出隊k個元素，但每個元素出入隊列只能有一次
        eg2: 動態數據尾部插入操作（C++中是vector，java中是ArrayList）
        一旦元素超過容量限制，則重新擴大并分配空間，將舊數據復制到新的內存地址上。
        有空間的情況下復雜度是O(1)
        空間滿了再擴大的時候的復雜度是O(n)
        重新分配k次的復雜度是O(2^n)

$$O(1)+O(2)+O(4)+...+O(2^n)=O(2^n-1)$$

GPU云服務器云服務器學習筆記一算法復雜度最大流算法時間復雜度最短路徑算法復雜度

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71032.html

筆記｜緩存

摘要：緩存算法我是，我會統計每一個緩存數據的使用頻率，我會把使用最少的緩存替換出緩存區。瀏覽器就是使用了我作為緩存算法。在緩存系統中找出最少最近的對象是需要較高的時空成本。再來一次機會的緩存算法，是對的優化。直到新的緩存對象被放入。緩存什么是緩存？ showImg(https://segmentfault.com/img/bVusZg); 存貯數據（使用頻繁的數據）的臨時地方，因為取原始...

elliott_hu 2019-08-06 13:15 評論0 收藏0
WebGL three.js學習筆記使用粒子系統模擬時空隧道（蟲洞）

摘要：學習筆記使用粒子系統模擬時空隧道本例的運行結果如圖時空隧道演示地址的粒子系統的粒子系統主要是依靠精靈體來創建的，要實現中的粒子系統創建，一般有兩種方式。 WebGL three.js學習筆記使用粒子系統模擬時空隧道本例的運行結果如圖：showImg(https://img-blog.csdnimg.cn/20190426222855492.png?x-oss-process=ima...

Guakin_Huang 2019-08-23 17:10 評論0 收藏0
深度學習的時間序列模型評價

摘要：技術總言這次主要說最近發展的無監督特征學習和深入學習，其對于時間序列模型問題的評價。建模連續數據的傳統方法包括從假定時間序列模型參數的估計，如自回歸模型和線性動力系統，和著名的隱馬爾可夫模型。此外，時間序列對時間變量有明顯依賴性。技術總言：這次主要說最近發展的無監督特征學習和深入學習，其對于時間序列模型問題的評價。這些技術已經展現了希望對于建模靜態數據，如計算機視覺，把它們應用到時間序列數...

zhaochunqi 2019-04-25 18:13 評論0 收藏0
【數據結構(C語言描述)】時空復雜度

摘要：目錄一時間復雜度例題二空間復雜度例題三常見復雜度對比一時間復雜度時間復雜度一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數。找到某條基本語句與問題規模之間的數學表達式，就是算出了該算法的時間復雜度。 ...

Y3G 2021-10-12 10:12 評論0 收藏0