Hello, World!

算法基础

字数统计: 1.3k阅读时长: 5 min
2018/04/16 Share

算法三原则

1，有穷性。
能在有限的步奏，有限的时间内完成。
2，确定性。
对相同的输入，产生唯一的输出，没有歧义。
3，可行性。
算法是可行的，在当前设备，经济水平等条件下是可用的。

算法分析

1，时间复杂度。
* 大O：最坏情况下的时间复杂度。（如快速排序：O(n^2)，期望nlogn）
* 忽略常数，用来描述随着问题规模的增长，所需时间增长的速率/数量级。 如：1-k -> O(1)，k是一个常数。

2，空间复杂度。
* 同时间复杂度。

算法极限

对于摸一个问题，算法能做到的也是有极限的，例如：通常基于遍历的算法，复杂度必定大于等于O(n)。

  • 不需要继续优化
    O(1) < O(logn) < O(n^1/2) < O(n) < O(nlogn)

  • 可能需要继续优化
    O(n^2) < O(n^3) < O(2^n) < O(n!)

时间复杂度

常见问题分析
* 输入输出有时候也是算法的一部分，需要考虑到复杂度内，例如：输入N个元素，则时间复杂度必定大于等于O(n)。
* 循环次数
* 均摊分析
* O(n) 线性查找
* O(n^2)冒泡、插入、选择，每个元素都要与其他所有元素进行一次比较。
* O(nlogn) 归并排序，快排的期望复杂度

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
- (void)bubbleSort:(int [])sortAry length:(int)length {
    BOOL needR = false;
    int count = length;
    // n个元素，需要n趟冒泡。
    for (int i = 0; i < count; count++) {
        needR = false;
        for (int j = 0; j <= count - 2 - i; j++) {
            if (sortAry[j] > sortAry[j + 1]) {
                [self swap:&sortAry[j] with:&sortAry[j + 1]];
            }
        }
        if (needR == false) {
            break;
        }
    }
}

- (void)swap:(int *)a with:(int *)b {
    int temp = *a;
    *a = *b;
    *b = temp;
}

冒泡排序的时间复杂度：O(n^2)。
冒泡排序的空间复杂度：O(n)，附加空间复杂度：O(1)。

经典二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
- (int)search:(int)b inArray:(int [])a start:(int)start end:(int)end {
    if (start == end) {
        if (a[start] == b) {
            return start;
        } else {
            return -1;
        }
    } else if (start > end) {
        return -1;
    }
    
    int middle = start + (end - start) / 2;
    if (a[middle] == b) {
        return middle;
    } else if (a[middle] > b) {
        return [self search:b inArray:a start:start end:middle-1];
    } else {
        return [self search:b inArray:a start:middle+1 end:end];
    }
}

递归中，每个元素往内存中压栈，空间复杂度比较高O(n)，慎重使用。
所有的递归均可转为while循环。

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 快速排序
- (void)sortCArray:(int [])a start:(int)start end:(int)end {
    if (start >= end) {
        return;
    }
    int low = start;
    int high = end;
    int keyIndex = start;
    
    while (low < high) {
        // 从高往低找比key小的元素
        while (a[high] >= a[keyIndex] && high > keyIndex) {
            high --;
        }
        if (a[high] < a[keyIndex]) {
            [self swap:&a[high] with:&a[keyIndex]];
            keyIndex = high;
        }
        while (a[low] <= a[keyIndex] && low < keyIndex) {
            low ++;
        }
        if (a[low] > a[keyIndex]) {
            [self swap:&a[low] with:&a[keyIndex]];
            keyIndex = low;
        }
    }
    // 一趟快速排序结束，以key为，将数组分为前后两部分，分别排序
    if (low == high) {
        [self sortCArray:a start:start end:keyIndex-1];
        [self sortCArray:a start:keyIndex+1 end:end];
    }
}

快速排序的时间复杂度：O(nlogn)。

插入排序

选择排序

二叉树

基本术语

树：除了根结点外，任意一个结点，有且只有一个父结点，可以有零个或者多个子结点。

结点的度：结点的分支数。

叶子结点：度为0的结点。

结点的层次：树中根结点的层次为1，根结点的子树的根为第2层，以此类推。

树的深度：树中所有结点层次的最大值。

树的度：树中所有结点度的最大值。

有序树、无序树：如果树中每棵子树从左往右的排序拥有一定的顺序，不得互换，则称为有序树，否则为无序树。

森林：是大于等于0棵互不相交的树的集合。

二叉树：每个结点最多有两棵子树，且有左右之分。

满二叉树：一个深度为K的二叉树节点数达最大（即2^k-1），则称为满二叉树。

完全二叉树：若二叉树的深度为h，除第h层外，其它各层的结点数都达到最大个数，第h层的所有结点都连续集中在最左边。

二叉排序树：
二叉排序树或者是一棵空树，或者具有下列性质的二叉树：
1.若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值。
2.若右子树不空，则右子树上所有结点的值均小于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。

二叉树的存储结构

二叉树通常采用两种存储方式：顺序存储结构和链式存储结构。

顺序存储结构就是数组存储。

链式存储结构就是链表存储。

原文作者：朱献国

原文链接：http://onzxgway.github.io/2018/04/16/arithmetic/

发表日期：April 16th 2018, 8:51:56 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 算法三原则
  2. 2. 算法分析
  3. 3. 算法极限
  4. 4. 时间复杂度
  5. 5. 冒泡排序
  6. 6. 经典二分查找
  7. 7. 快速排序
  8. 8. 插入排序
  9. 9. 选择排序
  10. 10. 二叉树
    1. 10.1. 基本术语
    2. 10.2. 二叉树的存储结构
Total : 29
2020
2019
2018
2017