算法与数据结构（1）

一：数据结构概论

数据结构分为初阶数据结构（主要由C语言实现）和高阶数据结构（由C++实现）

初阶数据结构当中，我们会学到顺序表、链表、栈和队列、二叉树、常见排序算法等内容。

高阶数据结构当中，我们会学到图、哈希表、红黑数等内容。

二：数据结构前言

1.数据结构：

数据结构是计算机存储与组织数据的方式（包括增加数据、删除数据、查找数据、改写数据等）指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有的用途都有用，所以我们要学习各种各样的数据结构，如：线性表、树、图、哈希……

数组 int arr[4]={0,1,2,3};就是一个简单的数据结构。

可以插入删除查找修改其中的元素。

但是数组元素只能时同类型的，数组这一单一的数据结构不是对所有的用途都有用，比如不同类型的数据，这时候我们就可以用另外一种数据结构————结构体。

2.算法：

算法就是定义良好的计算过程，它取一个或一组的值为输入，并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

算法是有好坏之分（效率高低之分）的，可以通过复杂度这一概念来判断算法的好坏。

算法和数据结构是紧密联系的，二者不可分割。

如何学好算法与数据结构？

1.死磕代码     2.画图画图画图+思考

三：算法效率

如何衡量一个算法的好坏呢？

案例：请看下面这道算法题：https://leetcode.cn/problems/rotate-array/description/

思路：循环K次每次将数组所有元素向后移一位。

代码点击执行可以通过，然而点击提交却无法通过，那该如何衡量其好与坏呢？

1.复杂度的概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间资源。

衡量一个算法的好与坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间：快慢————5ms V，S 5s

空间：占用内存大小————1G VS 1kB

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间

在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的 迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.复杂度的重要性

复杂度在校招中的考察已经很常见。

3.时间复杂度

定义：在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度衡量程序的时间效率，我们其实可以在程序中计算程序的运行时间。

用到C语言中的一个库函数clock（）#include <time.h>.

返回的时间单位是毫秒。

既然我们可以在程序中计算一个算法的运行时间，那为什么还要引入时间复杂度这一概念呢？

其实使用clock（）来计算算法的运行时间有一些弊端：

1.这种计算算法运行时间的方法只能在编写完程序后再去计算。

2.当代电脑CPU处理数据的速度一秒可以执行上亿次，对于循环次数较少的程序几种不同的算法打印出的结构可能都是0，就没有办法比较算法的好坏了。

3.程序运行时间和编译环境和运行机器的配置都有关系，比如同一个算法程序，用一个老编译器和新编译器编译，在同一台机器侠运行时间就不同。同一个程序，用低配置的设备和高配置的设备运行，时间也不同。

那我们有没有办法在想出有一种算法后就知道该算法的时间复杂度，进而判断这个算法的好坏呢？

这时候就要用到时间复杂度来进行判断。

算法的时间复杂度是一个函数式T(N)，这个函数计算了程序的执行次数。通过C语言的学习，我们知道算法编译后会形成二进制指令，程序运行，CPU就去执行这些指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每 句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执⾏次数和运⾏时间就是等⽐正相关， 这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的 算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b。

接下来我们通过几个程序的案例来进一步加深对于一个算法时间复杂度的理解。

案例一：

首先这个算法创建了变量count，又进行了N次循环，这N次循环中每次循环又嵌套了N次循环，循环过后又进行了2*N次循环，然后创建变量M，在进行M次循环。（M是一个确定的数）

据此我们可以得出本程序的基本操作次数（执行次数）T(N)=1+N^2+2*N+1+10

通过对N的取值分析，当N越来越大时，对结果影响最大的一项是N^2。

实际上我们计算复杂度时，也只是粗略的计算算法大概的执行次数，精确计算是很麻烦的（不同的一个语句编译出的二进制指令是不同的）（CPU处理数据时一秒可以处理上亿条指令）是可以允许一些计算误差的。

所以我们计算算法的时间复杂度时，只需要计算程序的大概执行次数就可以了，复杂度的表示通常使用大O的渐进表示法：

大O的渐进表示法：

推导大O规则

1.时间复杂度函数时T（N）中，只保留最高阶项，去掉那些低阶项，因为当N不断增大时，低阶项对结果的影响越来越小，当N无穷大时，就可以忽略不计了。

2.如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断增大时，这个系数对结果的影响越来越小，当N无穷大时，就可以忽略不计了。

3.T（N）中如果没有N相关的项目，只有常数项，用常数项1取代所有加法常熟。

通过以上分析，案例一的时间复杂度为O(N^2).

案例二：

分析：本算法进行了2*N次循环，又进行了M次循环，还进行了两次变量创建，一次打印。

T(N)=1+2*N+1+M+1

忽略掉可忽略项 T(N)=2*N+M (M=10)

又因为M是已知的。

所以根据大O的渐进表示法可得本算法的时间复杂O（N）。（注意不是O（2*N））

案例三：

本算法根据大O的渐近表示法可得时间复杂度为O(M+N).

需要分类讨论{1.M>>N时———O(M)   2.M<<N时——O(N）  3.M和N差不多时—O(M）或O(N)}

案例四：

本算法的执行次数为T(N)=100;

根据大O的渐近表示法可的本算法的时间复杂度为O(1).

案例五：

本算法的目的是进行查找字符在字符串中出现的位置

该算法的执行次数不是一个固定的值，而是需要根据实际的情况来确定，如果要查找的字符出现在字符串的前端，执行次数相对就少。反之，如果要查找的字符串出现在字符串的后端，执行的系数就会较多。

如果要查找的字符出现在字符串的第一个位置，T(N)=1.

如果要查找的字符出现在字符串的最后位置，T(N)=N.

如果要查找的字符出现在字符串的中间，T(N)=N/2.(N为字符串的长度)

因此，本算法的时间复杂度分为：

最好情况：O(1)

中间情况：O(N)

最坏情况：O(N)

案例六：

冒泡排序的时间复杂度：

趟数：n-1    每趟内部n-1-i次

也是分情况讨论：

1.若数组有序：则T(N)=N;

2.如果数组有序且为降序：则T(N)=N*(N-1)/2;

3.数组介于有序和无序之间。

判断一个算法的好坏要看最差的那种情况，因此本算法的时间复杂度取O（N^2）。

案例七：

本算法的执行次数直接分析的话不太容易

我们给n取值，查找其中的规律：

n==1时   T=0（T指循环执行次数）

n==2时   T=1

n==4时   T=2

n==5时   T=3

由此我们可以推断出规律  假设循环执行X次n=2^X，因此执行次数T=log2X（2是底数，X是真数）

因此：func5的时间复杂度取最差情况为： O (log 2 n )

案例八：