路漫漫其修远兮，吾将上下而求索。                         ——屈原

 

目录

一.什么是数据结构？

二.什么是算法？

1.算法的复杂度

2.时间复杂度

3.时间复杂度的练习

4.空间复杂度

---

一.什么是数据结构？

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

它指的是数据元素之间的相互关系，即数据的组织形式。这种组织形式就是数据的逻辑结构。

数据的逻辑通常有下面四类基本结构：

1.集合机构

2.线性结构

3.树状结构

4.图状结构

在计算机的实际处理数据的过程中，我们必须考虑数据应以什么方式进行存储能使之体现数据之间的关系。

数据在计算机的存储方式，就是数据的存储结构。就比如后面要学的顺序表，链表等等。

除此之外，在数据的处理过程中，还会出现数据的删除，插入，查找等操作，因此我们还应该考虑数据处理的方式，即算法。

二.什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。. 也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

像冒泡排序，查找一个数，查重等等都是算法。

算法的特征：

有穷性：算法必须能在执行有限个步骤之后终止。

确切性：算法的每一步骤必须有确切的定义。

输入项：一个算法有0个或多个输入，以刻画运算对象初始情况。

输出项：一个算法有1个或多个输出以反映对输入数据加工后的结果，没有输出的算法是毫无意义的。

可行性：算法中执行的任何计算步骤都可被分解为基本的可执行的操作步骤。

1.算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

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

2.时间复杂度

时间复杂度的定义:在计算机科学中，算法的时间复杂度是一个函数(数学函数)， 它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

总结：算法不是运行时间的多少，因为当你在运行代码的时候，时间的快慢也跟你此时的电脑配置和网速有关。所以只需要找到算法的运行次数。即某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

实例：计算一下Fun1中count++语句一共执行了多少次？

void Func1(int N){int count = 0;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){count++;}}for (int k = 0; k < 2 * N; k++){count++;}int M = 10;while (M--){count++;}printf("%dn", count);}

上面循环总次数：数学函数的表达式F(N)=N^2+2*N+10。

时间复杂度就是F(N)=N^2+2*N+10。

当N取不同的值时：

N = 10          F(N) = 130N = 1000      F(N) = 1002010N = 100000  F(N) = 10000200010

这里我们可以看出，随着N的逐渐增大，F(N)=N^2+2*N+10中的2*N+10对整个函数值的影响越来越小。时间的复杂度越来越靠近于N^2，我们就可以说N^2就是这个算法的时间复杂度。

对时间的复杂度我们用大0的渐进表示法：
大0符号(Big 0 notation) :是用于描述函数渐进行为的数学符号。

推导大0阶方法: 
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大0阶。

使用大0的渐进表示法以后，Func1 的时间复杂度为:O(N^2)。

通过上面我们会发现大0的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)

例如:在一个长度为N数组中搜索一个数据x
最好情况: 1次找到
最坏情况: N次找到
平均情况: N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为0(N)。

3.时间复杂度的练习

1.Func2的时间复杂度是多少？

void Fun2(int N){int count = 0;for (int k = 0; k < 2 * N; k++){count++;}int M = 10;while (M--){count++;}printf("%d\n", count);}

准确的F(N)=2*N+10。

随着N的不断增大，F(N)的大小跟10没有什么关系，所以在表示时间复杂度时，10是要去掉的，又根据推导大0阶方法中的第三点：3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大0阶。所以2*N中的2也可以取掉。

故Func2的时间复杂度就是O(N)。

2.计算Func3的时间复杂度是多少？

void Func3(int N, int M){int count = 0;for (int k = 0; k < M; k++){count++;}for (int k = 0; k < N; k++){count++;}printf("%d\n", count);}

很明显M和N没有什么明显的关系，所以时间复杂度就是O(N+M)。

1.如果N远大于M的话，时间复杂度就是O(N)。

2.如果M远大于N的话，时间复杂度就是O(M)。

3.如果M和N的大小差不多，时间复杂度就是O(N)或者O(M)。

3.计算strchr的时间复杂度？

strchr函数的功能就是在一个字符串里面查找一个指定的字符，如果查到了这个字符，就返回第一次字符出现的地址。找完了字符串也没发现这个字符，就返回空指针。

#include<string.h>//NULL空指针需要的头文件#include<assert.h>//assert必须要的头文件char* strchr(const char* str, int character){ //字符的ASCll值就是数子，所以这里字符的数据类型可以用intassert(str);while (*str){if (*str == character)return str;elsestr++;}return NULL; }

 在计算时间复杂度时，我们都是以最坏的情况来计算，所以strchr这个算法的时间复杂度是O(N)。

3.计算冒泡排序的时间复杂度？

void Bulllesort(int *arr,int N){    assert(arr);    for (int i = 0; i < N; i++)    {        for (int j = 0; j < N - i; j++)        {            if (arr[j] > arr[j + 1]) {                int ret = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = ret;            }        }    }

 这里可以看出当进入第一次冒泡排序时，数组需要交换9次，第二次进入冒泡排序时，数组需要交换8次，依次类推。其实这就是一个等差数列。F(N)=N(1+N)/2,所以时间复杂度为O(N^2)。

4.计算二分查找的时间复杂度？

int Binarysearch(int nums[], int size, int target) {    int left = 0;    int right = size - 1;    while (left <= right) {        int middle = left + ((right - left) / 2);        if (nums[middle] > target)        {            right = middle - 1;        }        else if (nums[middle] < target)        {            left = middle + 1;        }        else {            return middle;        }        }}

我们在计算时间复杂度都是已最坏的情况来计算的，在二分查找中，最坏的情况就是查找的数正好在最中间。也就是2^x=N,x就是查找的次数，在数学中都是log以2为底的对数，但是这在键盘不好打出来，于是就简化为log2，所以二分查找的时间复杂度就是O(log2)。

4.空间复杂度

空间复杂度也是一个数学函数表达式， 是对一个算法在运行过程中临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义。所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大0渐进表示法。
注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
 

void Bulllesort(int *arr,int N){    assert(arr);    for (int i = 0; i < N; i++)    {        for (int j = 0; j < N - i; j++)        {            if (arr[j] > arr[j + 1]) {                int ret = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = ret;            }        }    }

像这个冒泡排序除函数里面的参数不算外，额外定义了两个变量i和j，所以空间复杂度就是O(1)。

现如今电脑的空间容量都是比较大的了，对于空间复杂度已经不是很看重了。

常见的复杂度对比：

 

 

创造不易，希望大家能给点点赞，感谢。