一、数据结构与算法介绍

1、程序=结构+算法

程序由存储数据的结构和解决问题的算法组成，在计算机的世界里，结构和算法存在"相辅相成"的关系。程序根据算法选择最合适的存储结构，算法依赖存储结构，选择最优的策略处理数据，达到占用空间少、计算时间少的目的。

2、逻辑结构与物理结构

数据元素之间相互联系的方式称之为逻辑结构，数据元素的逻辑结构通过相互之间的关系分为：

2.1、集合，元素之间没有关系，单独存在；

2.2、线性结构，数组或链表表示的是1对1的关系；

2.3、树，二叉树是1对2的关系，普通树是1对多的关系；

2.4、图，图是多对多关系，节点表示元素，边表示节点之间的关系，有向边可以表示有向图。

type.jpg

数据元素在计算机中的存储方式是物理结构，数据按照在计算机中的存储结构可以分成两类，分别是线性存储结构和链式存储结构。

3、常见算法和算法的重要性

例如：计算1+2+3+...+1000的和

方法一：

Public int add(){
  int sum = 0;
  for(int i=1;i<=1000;i++){
    sum +=i;
  }
  return sum;
}

方法二：

Public int add(){
  int sum = 0；
  sum = 1000*（1+1000）/2
  return sum;
}

分析：

假定方法内每一条语句执行时间为1unit_time,

方法一循环执行了(1+2*1000+1)unit_time，方法二执行时间（1+1+1）unit_time;从上面两种方式计算sum，可以得出：好的算法真的很重要

二、时间复杂度分析

1、时间复杂浅析

渐进时间复杂度是随着数据规模N增大而变化的趋势，是衡量一个算法好坏的标准。时间复杂度包含最好时间复杂度、平均时间复杂度、最坏时间复杂度。

Public int find（int[] arr,int n,int data）{
  for（int i=0;i<n;i++）{
    if(arr[i] == data) {
    return i;
    break；
    }
  }
  return -1;
}

上面方法是从数组中查找数据，如果找到数据返回数组下标，如果没找到，则返回-1。arr是数组引用，n是数组长度，data是待查找数据。

最好时间复杂度：当开始遍历数组时，正好第一个数就是我们需要的查找的数据，时间复杂度O(1)；

最坏时间复杂度：当遍历完数组，还是没有找到我们需要的数据，时间复杂度O(n)；

平均时间复杂度：平均复杂度计算方法，(1+2+3+...+n-1+n)/n=n*(n+1)/2n，时间复杂度O(n)。

2、时间复杂度大O表示法

推导大O阶，我们可以按照如下的规则来进行推导，得到的结果就是大O表示法：

1、用常数1来取代运行时间中所有加法常数。

2、修改后的运行次数函数中，只保留最高阶项

3、如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常见时间复杂度比较：

O（1) < O(lgn) < O(n) < O(nlgn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

image

三、空间复杂度分析

类似时间复杂度，空间复杂度是一个算法占用存储空间，和数据规模N成渐进关系。

空间复杂度占用空间包含三个方面：

1、算法本身占用空间；

2、算法输入输出占用空间；

3、在计算的过程中，临时申请的内存占用的空间。

算法在执行的过程中，占用的空间不随数据规则N变化而变化，这样的算法是"就地"进行的。算法空间复杂度是一个常量，占用空间不随数据规模变化而变化，空间复杂度则为O(1),分析占用空间方法和时间复杂度类似。