admin管理员组文章数量:1794759
【数据结构】时间复杂度和空间复杂度（几乎最全，包含各种类型示例）讲解
1. 数据结构前言
1.1 数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希等
1.2 算法
算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
1.3 数据结构和算法的重要性
- 考研几乎必考（不管是408还是自主命题）
- 校园招聘笔试和面试必考
1.4 如何学好数据结构和算法
秘诀1：
死磕代码！！！！！！！！！！
秘诀2：
画图画图画图+思考
1.5 书籍推荐
1.《数据结构》严蔚敏
推荐理由：C语言版本，内容详尽，代码规整，各大院校指定教材
2.《数据结构》殷人昆
推荐理由：C++版本，内容详尽，代码规整
3.《算法导论》ThomasH. Cormen (托马斯•科尔曼)
推荐理由：叙述严谨，内容全面，深入讨论各类算法
4.《大话数据结构》程杰
推荐理由：趣味易读，算法讲解细致 深刻
2. 算法效率
如何衡量一个算法的好坏呢？
代码语言：javascript代码运行次数：0运行复制案例：旋转数组/ 思路：循环K次将数组所有元素向后移动⼀位
void rotate(int* nums, int numsSize, int k) {
while (k--)
{
int end = nums[numsSize - 1];
for (int i = numsSize - 1; i > 0; i--)
{
nums[i] = nums[i - 1];
}
nums[0] = end;
}
}代码点击执行可以通过，然而点击提交却无法通过，那该如何衡量其好与坏呢？
2.1 复杂度的概念
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2.2 复杂度的重要性
复杂度在校招中的考察已经很常见，如下：
3. 时间复杂度
定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率， 那么为什么不去计算程序的运行时间呢 ？
- 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同一个算法程序，用一个老编译器进行编译和新编译器编译，在同样机器下运行时间不同。
- 同一个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。
- 并且时间只能程序写好后测试，不能在写程序前通过理论思想计算评估。
那么算法的时间复杂度是一个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执行次数。通过c语言编译链接章节学习，我们知道算法程序被编译后生成二进制指令，程序运行，就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)，假设每句指令执行时间基本一样(实际中有差别，但是微乎其微)，那么执行次数和运行时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决一个问题的算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b。
案例：
代码语言：javascript代码运行次数：0运行复制// 请计算一下Func1中++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;
}
}Func1 执行的基本操作次数：
- N = 10 T(N) = 130
- N = 100 T(N) = 10210
- N = 1000 T(N) = 1002010
通过对N取值分析，对结果影响最大的一项是
实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的(不同的一句程序代码，编译出的指令条数都是不一样的)，计算出精确的执行次数意义也不大，因为我么计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别，上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。
3.1 大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号
[!IMPORTANT]
本文标签： 数据结构时间复杂度和空间复杂度（几乎最全，包含各种类型示例）讲解
版权声明：本文标题：【数据结构】时间复杂度和空间复杂度（几乎最全，包含各种类型示例）讲解 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754681048a1705125.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论