数据结构与算法—基础篇

一、数据结构

概念

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。数据结构分为逻辑结构和物理结构。

数据结构组成

• 数据: 程序的操作对象,用于描述客观事物。可以输入到计算机 ，可以被计算机处理。
• 数据对象: 性质相同的数据元素的集合(类似于数组)。
• 数据元素: 组成数据的对象的基本单位。

• 数据项: 一个数据元素由若干数据项组成。
  

  数据、数据对象、数据元素和数据项的关系如下图：
  

  数据结构

逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。数据的逻辑关系包括：

• 集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；（无序的）
• 线性结构：数据结构中的元素存在一对一的相互关系；
• 树形结构：数据结构中的元素存在一对多的相互关系；
• 图形结构：数据结构中的元素存在多对多的相互关系。

物理结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。

数据的物理结构的特点是：

• 顺序存储：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。比如数组存储在一串连续的内存中就属于顺序存储。
  

• 非顺序存储：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。比如非循环单向链表元素存储的内存地址就可以不是连续的，可以根据元素内指向下个元素的地址找到下个元素。
  

常见数据结构

二、算法

概念

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

数据结构和算法的关系

• 数据结构和算法两个概念间的逻辑关系贯穿了整个程序世界，首先二者表现为不可分割的关系。没有数据间的有机关系和高效处理，程序根本无法设计。
• 数据结构为算法提供服务。算法围绕数据结构操作。

• 解决问题和提高程序运行速度需要选择正确的算法，而高效率和低资源耗费的算法的设计又依赖于数据的结构。例如：算法中经常需要对数据进行增加和删除用链表数据结构效率高，数组数据结构因为增加和删除需要移动数字每个元素所以效率低。
  

  数据结构和算法的关系就像下图：
  

  数据结构和算法的关系

算法知识点

• 算法的特性

输入输出：算法可以有0个或者多个输入；算法至少要有一个输出，没有输出的算法也就没有意义。
有穷性：算法必须要在执行有限个步骤之后产生出结果。
确定性：算法的每个步骤都要有确切的意义。
可行性：算法的每个步骤都要切实有效，可执行。

• 算法的设计要求

正确性：算法被要求结果一定正确，不正确就没有意义了。
健壮性：算法内的逻辑处理要考虑到对不合理数据的处理，即容错能力。
可读性：即算法可供其他人阅读的能力。
时间复杂度：执行算法所需要的计算工作量或时间长短。一般用O(n)表示，n越大时间复杂度越大。一般作为衡量算法效率的主要方法。
空间复杂度：执行算法所需要的辅助（额外使用的）内存空间大小。也可用O(n)表示，计算比时间复杂度简单。

算法的时间复杂度

时间复杂度计算规则

• 用常数1取代运行时间中所有常数；eg：3->1 O(1)
• 在修改运行次数函数中,只保留最高阶项；eg: n^ 3+2n^2+5 -> O(n^3)
• 如果在最高阶存在且不等于1,则去除这个项目相乘的常数；eg：2n^3 -> O(n^3)

时间复杂度常见计算情况

• 常数阶
  时间复杂度为一个确定的常数，最终结果为O(1)。

//时间复杂度  1+1+1+1+1+1 = 6  O(1)
void testSum1(int n) {int sum = 0;   //执行1次sum = (1 + n) * 2; //执行1次sum = (1 + n) * 2; //执行1次sum = (1 + n) * 2; //执行1次sum = (1 + n) * 2; //执行1次sum = (1 + n) * 2; //执行1次
}

• 线性阶
  时间复杂度是n的一次幂的表达式，结果是O(n)。

//时间复杂度  1 + n = n   O(n)
void testSum2(int n) {int x = 0;for (int i = 0; i < n; i ++) {x = x + 1; //执行n次}
}
//时间复杂度  1 + (n + 1) + n = 2n + 2  O(n)
void testSum3(int n) {int x = 0;  // 1次for (int i = 0; i <= n; i ++) {x = x + 1; //执行 n + 1 次}for (int j = 0; j < n; j ++) {x = x * 2; //执行 n 次}
}

• 平方阶
  时间复杂度是n^2 的表达式，结果是O(n^2)。

//时间复杂度  1 + n + n^2   O(n^2)
void testSum4(int n) {int x = 0; // 1次for (int i = 0; i < n; i ++){x = x + 1;  //执行 n 次for (int j = 0; j < n; j ++){x = x + 1; //执行 n^2 次}}
}
//时间复杂度  n*(n+1)/2 = n^2/2 + n/2  O(n^2)
void testSum5(int n) {int x = 0;for (int i = 0; i < n; i ++) {for (int j = i; j < n; j ++) {x = x + 1;/** 等差数列求和i = 0, 执行n次i = 1， 执行n-1次i = 2， 执行n-2次...i = n-1, 执行 1 次执行总次数：n*(n+1)/2*/}}
}

• 对数阶
  时间复杂度是一个数的对数， o(logn)。

//时间复杂度 假如x是执行次数  2 ^ x >= n , x = log(2)(n)  O(logn)
void testSum6(int n) {int count = 1;while (count < n) {count = count * 2;  //执行 log(2)(n)次}
}

• 立方阶
  时间复杂度是包含n^3的表达式， O(n^3)。

//时间复杂度 n + n*n + n*n*n     O(n^3)
void testSum7(int n) {int x = 1;for (int i = 0; i < n; i ++) {x = x + 1; //n次for (int j = 0; j < n; j ++) {x = x + 1;//n*n次for (int k = 0; k < n; k ++) {x = x + 1;//n*n*n次}}}
}

时间复杂度的大小如下：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

算法的空间复杂度

一个算法执行的过程中可能用到的空间因素有：

• 寄存本身的指令
• 常数
• 变量
• 输入
• 对数据进行操作的辅助空间
  而算法的空间复杂度的计算主要是考虑算法执行时所需要的辅助空间。

例子：数组逆序,将一维数组a中的n个数逆序存放在原数组中（n<=a.count）。
方法一：只使用了一个中间变量temp，空间复杂度 O(1)

    int temp;for(int i = 0; i < n/2 ; i++){temp = a[I];a[i] = a[n-i-1];a[n-i-1] = temp;}

方法二：数组b中创建了n个元素，空间复杂度是O(n)

    int b[10] = {0};for(int i = 0; i < n;i++){b[i] = a[n-i-1];}for(int i = 0; i < n; i++){a[i] = b[i];}

总结

• 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
• 算法是是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
• 数据结构为算法提供服务。算法围绕数据结构操作。二者密不可分，贯穿整个程序运行。
• 算法的效率衡量的主要方法是计算算法的时间复杂度。