数据结构01-数据和算法

2017-08-25 本文已影响71人硅谷小虾米

最近工作不是很忙，所以经常会上简书翻翻有没有好的技术文章。一次偶然点开个人中心，发现自己第一篇文章发布到现在差不多整整一年了。想想这一年来真是也无风雨也无晴。因为琐事比较多再加上自己比较懒所以并没有坚持下去，其实学习技术和学英语是一样的，需要open your mouth,只有张开嘴和别人交流才能获得进步。再加上自己以前买的书再不看真的要发霉了，所以今后每周都会写一写自己的学习内容和大家分享，这些内容可能包括iOS、Web、TCP/IP、算法和数据结构等内容。一是作为自己的学习笔记，二来希望能得到大家的批评指正。

let it go

这篇文章作为数据结构部分的第一篇文章，主要会简单介绍一下数据结构，大部分都是概念性的一些东西，所以会以笔记的形式记录一下。还会包括一些算法(数据结构和算法关系很紧密)、线性表的一些知识。那什么是数据结构？简单的说就是下面这句话：

是相互之间存在一种或多种特定关系的数据元素的集合

如果你想要了解的更具体，可以点击这里。

数据：是描述客观事物的符号，是计算机中可操作的对象，能被计算机识别，并输入给计算机处理的符号合集
数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录
数据项：一个数据元素可以由若干个数据项组成

它们之间的关系如下图:
关系图
数据结构中的数据组织形式又分为逻辑结构和物理结构。

逻辑结构是指数据对象中数据元素之间的相互关系。可以分为以下四种:
1. 集合结构:元素同属于一个集合，但之间没有任何关系或关联。元素无规则的散部在集合之内。
2. 线性结构:数据元素之间一对一，首尾相连。
3. 树形结构:数据元素之间存在一对多的连接关系
4. 图形结构（又叫网络结构）:数据元素之间是多对多的关系。
  
  说完了逻辑结构再说说物理结构:是数据的逻辑结构在计算机中的存储形式。物理结构也有两种：
  
  1.顺序存储结构：把数据存放在地址连续的存储单元之中，每一个元素之间首尾相连，这种存储方式要求存储空间的容量要大于等于该集合中内容的容量。
  
  2.链式存储结构：把数据存放在任意的存储单元之中，可连续，可不连续。这种存储方式比顺序存储结构更加灵活，充分利用零散的物理存储空间，需要注意的是每一个元素利用空间存储自身的内容之外还需要分配空间用来存储该集合下另一个元素的物理存储地址。
  
  数据结构和算法密不可分，合理的数据存储结构和算法能够大幅度的提高逻辑运算、数据读写的消耗时间。下面简单说一部分算法
  
  什么是算法：
  
  算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量
  
  现在有一个需求是求出1+2+3+......+100的和，如果不经过思索，不考虑性能我们很快会写出下面这段代码:
```
    int sum = 0;
    for (int i = 0; i <= 100; i ++) {
        sum = sum + i;
    }
    printf("%d\n",sum);
```
  这样的方式当然没有问题，但是这段程序如果需要计算出正确的答案，整个for循环需要101次，显然这种方式会花费很多时间，认真看这个问题可以发现1+2+3+......+100的规律可以理解成首尾相加都是101.把这段计算从中间对折。也就是50个101相加代码实现如下：
```
    int sum = 0;
    sum = (1 + 100) * 100 / 2;
    printf("%d\n",sum);
```
  结果也是5050，但这一次程序没有发生循化，只运行了一次。显然，算法提高了效率。
  
  算法的特性
  
  1.输入项:一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件
  
  2.输出项:一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的
  
  3.有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止
  
  4.确切性：算法的每一步骤必须有确切的定义
  
  5.可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）
  
  上面这些是算法的特征，那么如果创造出一个算法如何评定这个算法是否是一个有效并合理的算法呢，评定一个算法有以下五个要求:
  
  1.正确性:能正确反映问题需求，能得到正确问题答案。
  
  2.可读性:供人们阅读的容易程度。
  
  3.健壮性:对不合理数据的反映能力和处理能力，容错性。
  
  4.高效率(时间复杂度)：相同数据处理量下能获得正确答案的时间越少，效率越高。
  
  5.低资源消耗(空间复杂度)：不占用过多的计算机计算能力。
  
  算法效率的度量方法###
  
  一般我们度量算法的效率有两种方式:1.事后统计方法(不推荐)，2.事前分析估算方法。这里我们通常采用第二种方式。
  
  还是回到1到100累加的问题，第一种普通运算方式下程序执行了n + 3次
```
  int sum = 0; // 1 次
  for (int i = 0; i <= 100; i ++) { // 100 + 1次
      sum = sum + i;
  }
  printf("%d\n",sum); // 1次
```
  第二种算法程序执行了3次
```
  int sum = 0; // 1次
  sum = (1 + 100) * 100 / 2; // 1次
  printf("%d\n",sum); // 1次
```
  显然随着n的次数增加第一种方法程序运行的次数会越来越来多，第二种方法不会随着n的增加而改变。
  
  现在如果有两个算法A：2n+3 B: 3n + 1。我们来比较一下这两个算法的效率。
  
  次数 2n+3 2n 3n+1 3n
  
  n=1 5 2 4 3
  
  n=2 7 4 7 6
  
  n=100 203 200 301 300
  
  结论：给定两个函数发f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N,f(n)总是比g(n)大，那么我们说f(n)的增长渐进快于g(n)
  
  时间复杂度###
  
  算法的时间复杂度也就是算法的时间度量，记作:T(n) = O(f(n))，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，叫做渐进时间复杂度。简称时间复杂度。我们用O()来体现时间复杂度的记法。
  
  时间复杂度的(大O阶)的方法:
  
  1.用常数取代运算时间中的所有加法常数。
  
  2.在修改后的运算次数函数中，只保留最高阶项。
  
  3.如果最高阶项存在并且部位1，则去除与这个项相乘的常数。
  
  下面举几个例子来说明常见的时间复杂度类型
  
  1.下面的时间复杂度是O(n + 3)->O(n) ，将常数项变为1，保留最高阶项。
```
 int sum = 0; // 1 次
  for (int i = 0; i <= 100; i ++) { // 100 + 1次
      sum = sum + i;
  }
  printf("%d\n",sum); // 1次
```
  2 O(3) -> O(1),常数项变为1，无最高阶项
```
 int sum = 0; // 1次
  sum = (1 + 100) * 100 / 2; // 1次
  printf("%d\n",sum); // 1次
```
  3.O(logn)
```
    int count = 1;
    while (count < 100) {
        count = count * 2;
    };
```
  常用的是时间复杂度所消耗的时间排序:
  
  O(1) < O(logn) < O(n) < O(nlogn) < O(nn) < O(nnn) < O(2的n次方) < O(n!) < O(n的n次方)*
  
  这篇文章的算法部分只是简单的介绍了，主要是为了配合数据结构。以后会专门写一些文章去记录算法的学习历程。下一篇文章会介绍一些线性表、单链表、双链表、栈和队列的相关知识。

数据结构01-数据和算法

算法效率的度量方法###

时间复杂度###

猜你喜欢

热点阅读

次数	2n+3	2n	3n+1	3n
n=1	5	2	4	3
n=2	7	4	7	6
n=100	203	200	301	300