数据结构(严)—绪论

首先，在写这篇博客之前，需要记录一下为什么要写哈哈。现在是24/2/16距离我成为北京大学的硕士还有312天，所以这篇数据结构的笔记，也是为了我的408考研。当然，学习数据结构当然不限于只拿个卷面高分，更重要的是算法Algorithm.

1.1 研究内容

  1.数据之间各种逻辑结构和物理结构，以及他们之间相应关系

  2.对每种结构定义相适应的算法(在以后的Algorithm practice中，写一道算法题，首先要写出所用的Algorithm frame)

   3.设计出相应的算法

  4.分析算法的效率(从时间复杂度和空间复杂度两个角度判断)

1.2基本概念和术语

  1.2.1数据、数据结构、数据项、数据对象、数据元素

    假设有两张表，一张为人员表，一张为课程表。这两张表就是数据。单独一张表就是数据对象，人员表就是一个数据对象，每张表的每一行为数据元素，而姓名，等属性就是数据项。

  1.2.2数据结构

    数据结构包括逻辑结构和存储结构两个层次。是相互之间存在一种或多种特定关系的数据元素的集合(不懂)

  逻辑结构（人的感官上，认为上分线性和非线性）

1. 集合结构：数据元素同属于一个集合，单个数据元素之间没有任何关系!
2. 线性结构：类似于线性关系，线性结构中的数据元素之间是一对一的关系。
3. 树型结构：数据元素存在一对多的关系
4. 图形结构(网状结构)：数据元素之间是多对多关系。

  存储结构（实际上计算机的内部存储结构）

1.   顺序存储结构：就是把数据元素放到地址连续的存储单元里面，数据间的逻辑关系和物理关系是一致的。例如数组。
2. 链式存储结构：就是把数据元素任意的放在存储单元里面，着组存储单元可以是连续的同样也可以是不连续的，根据指针找出相邻位置。

  1.2.3数据类型和抽象数据类型

1. 数据类型：包括整形Integer，字符型Byte，实型、数组、结构体、指针等。
2. 抽象数据类型(Abstract data type ADT):类似于c++中的类。

  1.3抽象数据类型的表示与实现

  抽象数据类型的概念与面向对象的‘类’思想是一致的。

  1.4算法和算法分析

  算法+数据结构=程序

  1.4.1算法的定义及特性

  算法是为了解决问题而规定的操作序列。(第一步第二步)

  必须满足五个特性：有穷性、确定性、可行性、输入、输出

  1.4.2评价算法优劣的基本标准

  正确性、可读性、健壮性、高效性

  1.4.3算法的时间复杂度和空间复杂度

  公司里有两个程序员，啸风和小风，二人各听老板安排写代码。最后啸风代码运行一次要花100ms,占用内存5MB，小风运行100s,占内存500MB。And then, the boss let 啸风 to go away.

  Although,如果代码都没有running，how to predict it's  useing times. 我们可以预估出代码基本操作执行次数。

　　做个比喻，场景1：一条长10寸的面包，小风每3天吃掉1寸，那么吃掉整个面包需要几天？ 3×10=30天。设面包长N寸，则需要3N天。如果用一个映射法则就是函数来表达，记作T(n)=3n。

　　场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一天8寸，第二天4寸，第三天2寸...那么小灰把面包吃的只剩下1寸，需要多少天？我们取其数值和变量，就是数字16不断除以2，除几次之后剩余1，就是log以2为低，16的对数，简写为log16。因此，把面包吃的只剩下1寸，需要5*log16=5*4=20天，如果面包长n寸呢？需要5*log(n)天，记作T(n)=5logn.

　　场景3：给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么吃掉整个鸡腿需要多少天？答案自然是2天，因为吃掉一只鸡腿自然和面包没有关系。T(n)=2。

　　场景4：依旧是一条10寸面包，吃掉第一个一寸需要1天，吃掉第二个1寸需要2天时间，吃掉第三个1寸需要三天...每多吃一寸，所花的时间也多一天。那么吃掉整个面包需要多少寸？答案是，从1累加到10的总和，也就是55天。如果面包长度是n寸？就是1+…+n=(1+n)*n/2=0.5n^2+0.5n。

　　我们把上面四个场景应用到程序设计中，刚好对应最常见的四种执行方式：

　　场景1：T(n)=3n,执行次数是线性的

　　场景2：执行次数是对数的T(n)=5logn

　　场景3：T(n)=2，执行次数是常量

 　　场景4：T(n)=0.5n^2+0.5n，执行次数是一个多项式

渐进时间复杂度(asymptotic time complexity，ATC)

 　　有了基本操作执行次数T(n)，是否就可以分析和比较一段代码的运行时间了呢？答nonono。比如算法A的相对时间是T(n)=100n，算法B的相对时间是T(n)=5n^2,这两个算法谁运行时间更长取决于n的值。

　　若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。渐进时间复杂度用大写O来表示，所以也被称为大O表示法。直白讲，时间复杂度就是把时间函数T(n)简化为一个数量级，这个数量级可以是n,n^2,n^3…。

如何推导出时间复杂度？有如下几个原则：1.如果运行时间是常数量级，用常数1表示；2.只保留时间函数中的最高阶项；3.如果最高阶项存在，则省去最高阶项前面的系数。例如T(n)=3n，简化为T(n)=O(n);T(n)=5logn，简化为T(n)=O(logn);T(n)=2，简化为T(n)=O(1);T(n)=0.5n^2+0.5n，简化为T(n)=O(n^2)。那么谁更节省时间呢？O（1）< O（logn）< O（n）< O（n^2） （看函数图像就欧克，更大的更节省时间）。

最好、最坏和平均时间复杂度

1. 最好时间复杂度，指的是算法计算量可能达到的最小值。
2. 最坏时间复杂度，指的是算法计算量可能达到的最大值。
3. 平均时间复杂度，是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。

　　空间复杂度：

空间复杂度只需要分析辅助变量所占的额外空间。

空间复杂度：S(n) = O(f(n))

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

我们再看一个代码：

int []m = new int[n];
for (i = 1; i <= n; ++i) {
j = i;
j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-5行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)