一睁蕾、前言

Pascal之父Nicklaus Wirth憑借一個公式獲得了圖靈獎（計算機(jī)領(lǐng)域的諾貝爾獎）
- 算法 + 數(shù)據(jù)結(jié)果 = 程序
大綱

大綱.png

二吧碾、搭建環(huán)境

開發(fā)工具
- eclipse（或者是IntelliJ IDEA）
- 為什么選eclipse
  - 明亮常柄、簡介琳猫、舒服
  - 多個項目可以在同一個窗口展示
  - 上課過程中不會使用到后臺開發(fā)的框架
- 支持Mac梅誓、Windows平臺
- JKD（版本>=1.8）

三沽讹、復(fù)雜度

什么是算法

引用百度百科對算法的解釋算法

算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令藻烤，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制绷雏。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入怖亭，在有限時間內(nèi)獲得所要求的輸出涎显。如果一個算法有缺陷，或不適合于某個問題依许，執(zhí)行這個算法將不會解決這個問題棺禾。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)峭跳。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量膘婶。

算法是用于解決特定問題的一系列的執(zhí)行步驟
- 例子

// 計算a和b的和
- (int)plus:(int)a b:(int)b {
    return a + b;
}

// 計算 1+2+3+...+n 的和
- (int)sum:(int)n {
    int result = 0;
    for (int i = 1; i<= n; i++) {
        result += i;
    }
    return result;
}

使用不同算法，解決同一個問題蛀醉，效率可能相差非常大悬襟。
- 例子：求第n個斐波那契數(shù)（fibonacci number）
- 斐波那契數(shù)：第n個數(shù)字是n-1和n-2的和；
- 摘自百度百科的解釋斐波那契數(shù)

斐波那契數(shù)拯刁，亦稱之為斐波那契數(shù)列（意大利語： Successione di Fibonacci)脊岳，又稱黃金分割數(shù)列、費(fèi)波那西數(shù)列垛玻、費(fèi)波拿契數(shù)割捅、費(fèi)氏數(shù)列，指的是這樣一個數(shù)列：1帚桩、1亿驾、2、3账嚎、5莫瞬、8儡蔓、13、21疼邀、……在數(shù)學(xué)上喂江，斐波那契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1旁振，F(xiàn)n=Fn-1+Fn-2（n>=2获询，n∈N*），用文字來說拐袜，就是斐波那契數(shù)列由 0 和 1 開始筐付，之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。

算法一：

/* 0 1 2 3 4 5
* 0 1 1 2 3 5 8 13 ....
*/
// 遞歸
- (int)fib1:(int)n {
    if (n <= 1) {
        return n;
    }
    // Fn = Fn-1 + Fn-2（n >= 2阻肿，n∈N*）
    return [self fib1:n - 1] + [self fib1:n - 2];
}

算法二

// 直接求值
- (int)fib2:(int)n {
    if (n <= 1) {
        return n;
    }
    
    int first = 0;
    int second = 0;
    // Fn = Fn-1 + Fn-2
    for (int i = 1; i < n; i++) {
        second += first;
        first = second - first;
    }
    
    return second;
}

補(bǔ)充：算法三

public static int fib3(int n) {
    if (n <= 1) return n;
      int first = 0;
        int second = 1;
        while (n-- > 1) {
            second += first;
            first = second - first;
        }
        return second;      
}

比較兩者時間所用到的方法，TimeTool.m

/// 計算執(zhí)行完 block 所需花費(fèi)時間
+ (void)calculateTimeWithTitle:(NSString *)title operationBlock:(void(^)(void))operationBlock {
    NSDateFormatter *formatter = [[NSDateFormatter alloc] init];
    [formatter setDateFormat:@"YYYY-MM-dd HH:mm:ss:mmm"];
    NSDate *startDate = [NSDate date];
    NSString *currentTimeString = [formatter stringFromDate:startDate];
    NSLog(@"%@ start, time = %@",title,currentTimeString);
    
    if (operationBlock) {
        operationBlock();
    }
    
    NSDate *endDate = [NSDate date];
    currentTimeString = [formatter stringFromDate:endDate];
    NSLog(@"%@ end, time = %@",title,currentTimeString);
    
    NSLog(@"%@ 耗時:%f second",title,[endDate timeIntervalSince1970] - [startDate timeIntervalSince1970]);
}

比較兩個算法的時間

- (void)viewDidLoad {
    [super viewDidLoad];
    
    int n = 35;
    // fib1
    [TimeTool calculateTimeWithTitle:@"fib1" operationBlock:^{
        [self fib1:n];
    }];
    
    // fib2
    [TimeTool calculateTimeWithTitle:@"fib2" operationBlock:^{
        [self fib2:n];
    }];
}

分析：經(jīng)過大量測試沮尿，發(fā)現(xiàn)上面的方法有缺陷,當(dāng)數(shù)字大的時候丛塌，用時時間過長，下面的方法就不用有這個問題畜疾；當(dāng)n<35的時候赴邻，兩個算法的執(zhí)行時間相差不大，但是隨著n的增加啡捶，相差時間越來越明顯了姥敛。當(dāng)n為64的時候，打印第一個方法是9.444秒瞎暑，第二個方法依然是0.0秒彤敛；

如何評判一個算法的好壞？

例子：求 1+2+3+...+n 的和

// 計算 1+2+3+...+n 的和
- (int)sum:(int)n {
    int result = 0;
    for (int i = 1; i<= n; i++) {
        result += i;
    }
    return result;
}

// 計算 1+2+3+...+n 的和
- (int)sum1:(int)n {
    return (1 + n) * n / 2;
}

事后統(tǒng)計法

比較不同算法對同一組輸入的執(zhí)行處理時間
上述方案有明顯的缺點(diǎn)
- 執(zhí)行時間嚴(yán)重依賴硬件以及運(yùn)行時各種不確定的環(huán)境因素
- 必須編寫相應(yīng)的測試代碼
- 測試事件的選擇比較難保證公正性

一般從以下維度來評估算法的優(yōu)劣

正確性了赌、可讀性墨榄、健壯性
時間復(fù)雜度(time complexity)：估算程序指令的執(zhí)行次數(shù)（執(zhí)行時間）
空間復(fù)雜度(space complexity)：估算所需占用的存儲空間

大O表示法

一般用大O表示法來描述復(fù)雜度，它表示的是數(shù)據(jù)規(guī)模n對應(yīng)的復(fù)雜度
忽略常數(shù)勿她，系數(shù)袄秩，低階
- 0 >> O(1)
- 2n + 3 >> O(n)
- n2 + 2n + 6 >> O(n2)
- 4n3 + 3n2 + 22n + 100 >> O(n3)
對數(shù)階一般省略底數(shù)，因?yàn)?log2 n = log2 9 * log9 n逢并，所以之剧，log2 n，log9 n統(tǒng)稱為 logn

注意：大O表示法僅僅表示一種粗略的分析模型砍聊，是一種估算背稼，能幫助我們短時間內(nèi)了解一個算法的執(zhí)行效率。

實(shí)例講解時間復(fù)雜度

test1 時間復(fù)雜度 O(1)

- (void)test1:(int)n {
// 1
    if (n > 10) {
        NSLog(@"n > 10");
    } else if (n > 5) { // 2
        NSLog(@"n > 5");
    } else {
        NSLog(@"n <= 5");
    }
    
    // 1 + 4 + 4 + 4 (指令執(zhí)行條數(shù))
    for (int i = 0; i < 4; i++) {
        NSLog(@"test1");
    }
}

test2 時間復(fù)雜度 O(n)

- (void)test2:(int)n {
    // 1 + 3n (指令執(zhí)行條數(shù))
    // O(n)
    for (int i = 0; i < n; i++) {
        NSLog(@"test");
    }
}

test3 時間復(fù)雜度 O(n^2)

- (void)test3:(int)n {
    // 1 + 2n + n * (1 + 3n) (指令執(zhí)行條數(shù))
    // 1 + 2n + n + 3n^2
    // 3n^2 + 3n + 1
    // O(n^2)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            NSLog(@"test");
        }
    }
}

test4 時間復(fù)雜度 O(n)

- (void)test4:(int)n {
    // 1 + 2n + n * (1 + 45) (指令執(zhí)行條數(shù))
    // 1 + 2n + 46n
    // 48n + 1
    // O(n)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 15; j++) {
            NSLog(@"test");
        }
    }
}

test5 時間復(fù)雜度 O(logn)

- (void)test5:(int)n {
    // 執(zhí)行次數(shù) = log2(n)
    // O(logn)
    while ((n = n / 2) > 0) {
        NSLog(@"test");
    }
}

test6 時間復(fù)雜度 O(logn)

- (void)test6:(int)n {
    // log5(n)
    // O(logn)
    while ((n = n / 5) > 0) {
        NSLog(@"test");
    }
}

test7 時間復(fù)雜度 O(nlogn)

- (void)test7:(int)n {
    // 1 + 2*log2(n) + log2(n) * (1 + 3n)
    // 1 + 3*log2(n) + 3 * nlog2(n)
    // O(nlogn)
    for (int i = 1; i < n; i = i * 2) {
        // 1 + 3n
        for (int j = 0; j < n; j++) {
            NSLog(@"test");
        }
    }
}

多個數(shù)據(jù)規(guī)模的情況

- (void)test8:(int)n k:(int)k {
    for (int i = 0; i < n; i++) {
        NSLog(@"test8 %d",i);
    }
    
    for (int i = 0; i < k; i++) {
        NSLog(@"test8 %d",i);
    }
}

時間復(fù)雜度為 O(n + k)

常見的復(fù)雜度

執(zhí)行次數(shù)	復(fù)雜度	非正式術(shù)語
12	O(1)	常數(shù)階
2n + 3	O(n)	線性階
4n2 + 2n + 6	O(n2)	平方階
4log2 n + 25	O(logn)	對數(shù)階
3n + 2nlog3 n + 15	O(nlogn)	nlogn階
4n3 + 3n2 + 22n + 100	O(n3)	立方階
2n	O(2n)	指數(shù)階

復(fù)雜度比較:
- O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)
可以借助函數(shù)生成工具對比復(fù)雜度的大小

復(fù)雜度圖形比較

數(shù)據(jù)規(guī)模較小時

image.png

數(shù)據(jù)規(guī)模較大時

image2.png

兩個算法的時間復(fù)雜度分析

fib1函數(shù)的時間復(fù)雜度分析

image3.png

fib2函數(shù)的時間復(fù)雜度分析

循環(huán)n次辩恼，所以時間復(fù)雜度為O(n)

算法的優(yōu)化方向

用盡量少的存儲空間
用盡量少的執(zhí)行步驟（執(zhí)行時間）
根據(jù)情況雇庙，可以空間換時間或時間換空間

擴(kuò)展

一個用于學(xué)習(xí)算法的網(wǎng)站
- https://leetcode.com/
- https://leetcode-cn.com/

《戀上數(shù)據(jù)結(jié)構(gòu)與算法》-復(fù)雜度

《戀上數(shù)據(jù)結(jié)構(gòu)與算法》-復(fù)雜度

一睁蕾、前言

二吧碾、搭建環(huán)境

三沽讹、復(fù)雜度

什么是算法

算法一：

算法二

補(bǔ)充：算法三

如何評判一個算法的好壞？

事后統(tǒng)計法

一般從以下維度來評估算法的優(yōu)劣

大O表示法

實(shí)例講解時間復(fù)雜度

多個數(shù)據(jù)規(guī)模的情況

常見的復(fù)雜度

復(fù)雜度圖形比較

兩個算法的時間復(fù)雜度分析

fib1函數(shù)的時間復(fù)雜度分析

fib2函數(shù)的時間復(fù)雜度分析

算法的優(yōu)化方向

擴(kuò)展