目录
1. 什么是数据结构？
1.1 数据结构和数据库的区别
1.1.1磁盘的特点：
2.什么是算法？
3.算法效率
3.1 如何衡量一个算法的好坏
4.时间复杂度
4.1 时间复杂度的概念
4.2 大O的渐进表示法
4.3常见时间复杂度计算举例
4.3.1.计算两个循环分别对应两个变量有关的的时间复杂度
4.3. 2. 计算只与常量数字有关的的时间复杂度
4.3.3. 计算strchr的时间复杂度
4.3.4计算冒泡排序BubbleSort的时间复杂度
4.3.5 计算二分法BinarySearch的时间复杂度
4.3.6计算阶乘递归的时间复杂度
4.3.7 计算斐波那契数列的时间复杂度
1. 什么是数据结构？
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的 数据元素的集合。
1.1 数据结构和数据库的区别
数据结构和数据库本质都是在管理数据，只是在不同的地方管理。
数据量很大的时候适合在磁盘当中管理，要用数据库。
数据相对小没有那么多，在运行内存中管理，就用数据结构。
数据结构：在内存中管理数据 —> 增删查改
数据库：在磁盘中管理数据 —> 增删查改
1.1.1磁盘的特点
磁盘可以不带电存储，内存不能。
举个例子：
写了一个文件，文件没有保存，这个时候文件储存在内存当中。
如果ctrl+s一下，就会把文件保存到磁盘里面去。
2.什么是算法？
算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为 输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
算法是针对这些数据进行处理。
简单的算法，排序。冒泡排序，快速排序
查找： 二分查找，暴力查找
数据结构和算法的关系，相辅相成。
3.算法效率
3.1 如何衡量一个算法的好坏
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
插播一个摩尔定律：
“摩尔定律是英特尔创始人之一戈登·摩尔的经验之谈，其核心内容为：集成电路上可以容纳的晶体管数目在大约每经过18个月便会增加一倍。摩尔定律是内行人摩尔的经验之谈，汉译名为“定律”，但并非自然科学定律，它一定程度揭示了信息技术进步的速度。”
4.时间复杂度
4.1 时间复杂度的概念
时间复杂度的定义：
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。
请注意：时间复杂度不是在算它的执行时间，因为执行时间是没有标准的，这个和我们的硬件设备和机器环境有关系。
一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法 的时间复杂度。
找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
举一个例子：
// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count; //这里count++执行N*N次
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count; //这里count++执行2*N次
}
int M = 10;
while (M--)
{
++count; //这里count++执行M次
}
//所以++count总共执行 N^2+2*N+M 次实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这 里我们使用大O的渐进表示法。
4.2 大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
O()括号里面的数更多的表达的是这个算法的量级，大O是一个估算，并不是准确的执行次数。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项系数存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
举一个例子：
// 计算Func2的时间复杂度？
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count; //2*N
}
int M = 10;
while (M--)
{
++count; //10
}
printf("%d\n", count);
}
//2*N+10
//当N趋于无限大的时候，10和2对于整体的效果影响不大，所以舍去得到N
//注意N和2*N+10是一个量级的
//
//所以Fun2的算法复杂度为 O(N)=N另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
举个例子：
在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。
一般情况关注的是算法的最坏运行情况，所以以最坏情况的时间复杂度为准。
4.3常见时间复杂度计算举例
4.3.1.计算两个循环分别对应两个变量有关的的时间复杂度
// 计算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);
}答案参考如下：
4.3. 2. 计算只与常量数字有关的的时间复杂度
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}答案参考如下：
4.3.3. 计算strchr的时间复杂度
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );答案参考如下：
4.3.4计算冒泡排序BubbleSort的时间复杂度
// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}答案参考如下：
4.3.5 计算二分法BinarySearch的时间复杂度
// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
// [begin, end]：begin和end是左闭右闭区间，因此有=号
while (begin <= end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid-1;
else
return mid;
}
return -1;
}答案参考如下：
4.3.6计算阶乘递归的时间复杂度
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}答案参考如下：
4.3.7 计算斐波那契数列的时间复杂度
因为这块内容较长，将单独列出。链接明天补^-^
斐波那契数列的时间复杂度为O(2^N)。
你好我是媛仔，希望这篇内容对你有所帮助！！今天现写到这里了，因为要帮忙哄小孩所以今天好累好累好累……
版权声明：本文为博主作者：vpurple__原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/vpurple_/article/details/125963016
