什么是数据结构？

结构，简单的理解就是关系。严格点说，结构是指各个组成部分相互搭配和排列的方式。在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系成为结构。

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

按照视点的不同，我们把数据结构分为逻辑结构和物理结构

逻辑结构

指数据元素之间的相互关系

1. 集合结构

集合结构中的数据元素除了同属于一个集合外，他们之间没有其他的关系，各个数据元素是平等的 集合结构

2. 线性结构

线性结构中的数据元素之间是一对一的关系

线型结构

3. 树形结构

树形结构中的数据元素之间存在一对多的层级关系

树形结构

4. 图形结构

图形结构中的数据元素是多对多的关系

图形结构

物理结构

指数据的逻辑结构在计算机中的存储形式

1. 顺序存储结构

数据元素存放在连续的存储单元中，其数据间的逻辑关系和物理关系是一致的

2.链式存储结构

是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。 数据的存储关系并不能反映其逻辑关系。

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

1. 算法特性

1.输入输出
2.有穷性 （时间）
3.确定性（不会出现二义性）
4.可行性 （可实现、可移植， 每一步都能够通过执行有限次数完成）

2. 算法设计的要求

1.正确性（输入、输出、加工处理无歧义，正确反映问题的需求，得到正确的答案）
2.可读性
3.健壮性
4.时间效率高和存储量低

3. 算法效率和度量方法

1.事后统计方法
2.事前分析估算方法

时间复杂度

推导大O阶：
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数

1.常数阶

常数阶看代码执行的行数，假如有3行代码 则O(3) => O(1);

2.线性阶

线性阶是循环结构会复杂很多，要确定某个算法的阶次， 需要确定某个特定语句或语句集运行的次数。因此分析算法的复杂度，关键就是要分析循环结构的运行情况

for(int i = 0; I < n; i++) {
   /* 时间复杂度为O(1)的程序*/
}
时间复杂度为O(n)

3. 对数阶

int count = 1;
while(count < n) {
  count = count * 2;
  /* 时间复杂度为O(1)的程序*/
}
由于每次count乘以2之后，就距离n更近了一份。也就是说 有多少个2相乘后大于n,则会退出循环。 由2^x = n, 得到 x = log2^n, 所以时间复杂度为 O(log n)

4. 平方阶

for(int i = 0; i< m; i++) {
   for(int j = 0; j < n; j++) {
     /* 时间复杂度为O(1)的程序*/
  }
}
时间复杂度为 O(m x n)

int i , j;
for(i = 0; i< n; i++) {
   for( j = i; j < n; j++) {
     /* 时间复杂度为O(1)的程序*/
  }
}
时间复杂度为 O(n^2);

for(int i = 0; i < n; i ++) {
   function(i);
}

void function(int count) {
   print(count);
}
时间复杂度为O(n);

for(int i = 0; i < n; i ++) {
   function(i);
}

void function(int count) {
   int j;
   for( j = count; j < n; j++) {
        /* 时间复杂度为O(1)的程序*/
   }
}
时间复杂度为O(n^2);

常见的时间复杂度