数据结构概念及算法优劣评价

发表于 | 分类于 | | 浏览 次
字数统计: 2,153 字 | 阅读时长 ≈ 9 分钟

本篇文章是重温数据结构系列的第一篇，也是对自己复习的记录，简单介绍下数据结构、算法等概念及如何判断算法的优劣，并用最大子列和问题作为例子，展示了各种不同时间复杂度的实例。

什么是数据结构

查阅资料会发现，关于数据结构的描述很多，比如：

1
2
数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。
                                            ----Sartaj Sahni，《数据结构、算法与应用》

1
2
数据结构是ADT（抽象数据类型Abstract Data Type）的物理实现。
                                        ----Clifford A.Shaffer，《数据结构与算法分析》
1
2
数据结构（data structure）是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最有效率的算法。
                                         -----中文维基百科

通过多种描述，可以发现：

  • 数据结构没有官方统一的定义
  • 数据结构和算法联系密切
1
2
3
解决问题方法的效率，跟数据的组织方式有关
解决问题方法的效率，跟空间的利用效率有关
解决问题方法的效率，跟算法的巧妙程度有关

到底什么是数据结构？？

  • 数据对象在计算机中的组织方式

    □ 逻辑结构

    □ 物理存储结构

  • 数据对象必定与一系列加在其上的操作相关联

  • 完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type）

  • 数据类型

    □ 数据对象集

    □ 数据集合相关联的操作集

  • 抽象：描述数据类型的方法不依赖与具体实现

    □ 与存放数据的机器无关

    □ 与数据存储的物理结构无关

    □ 与实现操作的算法和编程语言均无关

    只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

算法（Algorithm）的描述

  • 一个有限指令集
  • 接受一些输入（有些情况下不需要输入）
  • 产生输出
  • 一定在有限步骤之后终止

  • 每一条指令必须

    （1） 有充分明确的目标，不可以有歧义

（2） 计算机能处理的范围之内

（3） 描述应不依赖于任何一种计算机语言以及具体的实现手段

如何判断算法的优劣

  • 空间复杂度S(n) —— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的
    规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

  • 时间复杂度T(n) —— 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规
    模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

在分析一般算法的效率时，我们经常关注下面两种复杂度

  • 最坏情况复杂度
    Tworst( n )
  • 平均复杂度
    Tavg( n )

例如，在一个长度为 n 的列表中顺序搜索指定的值，则

最坏情况：n 次比较

平均情况：n/2 次比较

最佳情况：1 次比较

而实际中，我们一般仅考量算法在最坏情况下的运行情况，也就是对于规模为 n 的任何输入，算法的最长运行时间。这样做的理由是：

（１）一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界（Upper Bound）。

（２）对于某些算法，最坏情况出现的较为频繁。

（３）大体上看，平均情况通常与最坏情况一样差。

算法分析要保持大局观（Big Idea），其基本思路：

  • 忽略掉那些依赖于机器的常量
  • 关注运行时间的增长趋势
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n )＜Ο(n!)

具体实例（最大子列和问题）

给定K个整数组成的序列{ N1, N2, …, NK }，“连续子列”被定义为{ Ni, Ni+1, …, Nj }，其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

  • 算法一（最直接的暴力办法）
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
33
34
35
36
37
38
39
40
41
#include <stdio.h>

int max_subsequence_sum(int list[], int n);

int main(void)
{
    int n;
    printf("please enter a num\n");
    scanf("%d", &n);
    int array[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }

    int result = max_subsequence_sum(array, n);
    printf("%d\n", result);
}

int max_subsequence_sum(int list[], int n)
{
    int this_sum, max_sum, i, j, k;
    max_sum = 0;
    for(i = 0; i < n; i++)
    {
        for (j = i; j < n; j++)
        {
            this_sum = 0;
            for(k = i; k<= j; k++)
            {
                this_sum += list[k];
            }
            if(this_sum > max_sum)
            {
                max_sum = this_sum;
            }
        }
    }
    return max_sum;
}

很明显该方法的时间复杂度为O(n^3)，在数据量稍大的时候这其实是非常耗时的算法，在我们开发设计的过程中最好不要设计出这样时间复杂度的算法。

  • 算法二
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
33
34
35
36
37
38
39
40
41
#include <stdio.h>

int max_subsequence_sum(int list[], int n);

int main(void)
{
    int n;
    printf("please enter a num\n");
    scanf("%d", &n);
    int array[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }

    int result = max_subsequence_sum(array, n);
    printf("%d\n", result);
}

int max_subsequence_sum(int list[], int n)
{
    int this_sum, max_sum, i, j, k;
    max_sum = 0;
    for(i = 0; i < n; i++)
    {
        for (j = i; j < n; j++)
        {
            this_sum = 0;
            for(k = i; k<= j; k++)
            {
                this_sum += list[k];
            }
            if(this_sum > max_sum)
            {
                max_sum = this_sum;
            }
        }
    }
    return max_sum;
}

该方法的时间复杂度为O( n^2 ) ,已经比上一个有进步了，还有没有更好的方法了，通常遇到n^2 的算法需要多想想优化方案，看能不能优化为O( nlog^n )的算法。

  • 算法三（分而治之）
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>

int max_subsequence_sum(int list[], int n);

int main(void)
{
    int n;
    //printf("please enter a num:\n");
    scanf("%d", &n);
    int array[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }

    int result = max_subsequence_sum(array, n);
    printf("%d\n", result);

    return 0;
}


static int max3(int a, int b, int c)
{
    int max = 0;
    max = a>b?a:b;
    max = max>c?max:c;
    return max;
}

static int max_sub_sum(const int A[], int left, int right)
{
    int max_left_sum, max_right_sum;
    int max_left_border_sum, max_right_border_sum;
    int left_border_sum, right_border_sum;
    int center, i;

    if(left == right)
    {
        if(A[left] > 0)
        {
            return A[left];
        }
        else
        {
            return 0;
        }
    }

    center = (left + right) / 2;
    max_left_sum = max_sub_sum(A, left, center);
    max_right_sum = max_sub_sum(A, center+1, right);

    max_left_border_sum = 0;
    left_border_sum = 0;
    for(i = center; i >=  left; i--)
    {
        left_border_sum += A[i];
        if(left_border_sum > max_left_border_sum)
        {
            max_left_border_sum = left_border_sum;
        }
    }

    max_right_border_sum = 0;
    right_border_sum = 0;
    for(i = center + 1; i <= right; i++)
    {
        right_border_sum += A[i];
        if(right_border_sum > max_right_border_sum)
        {
            max_right_border_sum = right_border_sum;
        }
    }

    return max3(max_left_sum, max_right_sum, max_left_border_sum + max_right_border_sum);
}

int max_subsequence_sum(int A[], int N)
{
    return max_sub_sum(A, 0, N-1);
}

该算法的时间复杂度为O( nlog^n ),其实已经很棒了，那么还有没有比该算法还更优的算法呢，如果没有比该比该算法更优的算法的话，该算法就会是提现递归威力的极好的范例了。然而，还真有更优的算法，见算法四

  • 算法四（在线处理算法）
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
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>

int max_subsequence_sum(int A[], int n);

int main(void)
{
    int n;
    //printf("please enter a num:\n");
    scanf("%d", &n);
    int array[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }

    int result = max_subsequence_sum(array, n);
    printf("%d\n", result);

    return 0;
}

int max_subsequence_sum(int A[], int N)
{
    int i, this_sum, max_sum;
    max_sum = 0;
    this_sum = 0;
    for(i = 0; i < N; i++)
    {
        this_sum += A[i];
        if(this_sum > max_sum)
        {
            max_sum = this_sum;
        }
        else if(this_sum < 0)
        {
            this_sum = 0;
        }
    }

    return max_sum;
}

该算法对每个输入的数据只处理一遍，时间复杂度为O(n),真是棒极了！

参考资料

[浙江大学数据结构公开课]

《数据结构与算法分析–C语言描述》

如果你觉得本文对你有帮助，欢迎打赏