软考-数据结构

软考-数据结构与算法

时间复杂度

T(n) f(n) O(n)
取最高次数项且不要系数

例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void aFunc(int n) {
    if (n >= 0) {
        // 第一条路径时间复杂度为 O(n^2)
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("输入数据大于等于零\n");
            }
        }
    } else {
        // 第二条路径时间复杂度为 O(n)
        for(int j = 0; j < n; j++) {
            printf("输入数据小于零\n");
        }
    }
}

对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度
此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)

例

1
2
3
4
5
6
7
8
9
10
void aFunc(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            printf("Hello World\n");
        }
    }
}

所以，执行次数 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。
根据上文说的 大O推导法可以知道，此时时间复杂度为 O(n^2)。

例

1
2
3
4
5
6
7
8
9
void aFunc(int n) {
    for (int i = 2; i < n; i++) {
        i *= 2;
        printf("%i\n", i);
    }
}

假设循环次数为 t，则循环条件满足 2^t < n。
可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。

例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}


显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。

        显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。

        所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。

空间复杂度

线性表

除了第一个元素都有前驱，除了最后一个元素都有后继
线性表的存储结构有:顺序和链式
数组、链表、栈、队列都是

广义表

是一种线性存储结构，可以存储不可再分的单元素也可以存储表格
广义表是线性表的推广
线性表的元素都是结构上不可分的单元素

A = ()：A 表示一个广义表，只不过表是空的。
B = (e)：广义表 B 中只有一个原子 e。
C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))

栈stack

栈的存储结构有顺序存储和链式存储两种
LIFO

队列queue

FIFO

树

二叉树