目录
一、前言
二、数据结构
2.1数据结构的概念
2.2数据结构的组成
2.3算法
三、oj题引进
四、复杂度
4.1复杂度的概念
4.2大O渐进表示法
4.3时间复杂度
4.4时间复杂度计算示例
4.4.1示例1
4.4.2示例2
4.4.3示例3
4.4.4示例4
4.4.5示例5
4.4.6示例6
4.4.7示例7
4.4.8示例8
4.5空间复杂度
4.6空间复杂度示例
4.6.1示例1
4.6.2示例2
4.7常见复杂度对比
五、再回oj
六、赠言

一、前言

hello啊，各位宝子们！还是那句话，今天的你还在坚持学习吗？今天的你又是否对枯燥的求学生活而感到烦恼呢？学习可不是一蹴而就的哦，在深入的学习之后，咱们也需要适当的放松，一昧的给自己施加压力，往往会适得其反。我相信大家都能够调整好自己，那么在这些之后，就来学习数据结构的第一节内容——算法复杂度吧！

二、数据结构

2.1数据结构的概念

数据结构是计算机科学中的一个重要概念，它涉及到数据的组织、管理和存储格式。在计算机中，数据结构是一种组织数据的方式，使得数据可以高效地被访问和修改。数据结构不仅仅是关于数据的存储，而是更多地关于数据之间的关系以及如何利用这些关系来更好地操作数据。

2.2数据结构的组成

数据结构主要由三个基本组成部分构成：
1、数据的逻辑结构：这是指数据元素之间的逻辑关系，它与数据的存储无关，是从具体问题中抽象出来的数学模型。逻辑结构可以分为集合、线性结构、树形结构和图形结构等类型。
2、数据的存储结构：也称为数据的物理结构，是指数据的逻辑结构在计算机中的存储表示。常见的存储结构包括顺序存储、链式存储、索引存储和哈希存储等。
3、数据的操作：定义在数据的逻辑结构上的一系列操作，包括创建、插入、删除、查找、修改和遍历等。

2.3算法

算法（Algorithm）是解决问题的一系列清晰指令，它代表着用系统的方法描述解决问题的策略机制。算法不仅是计算的核心，而且是计算机程序的基础。在计算机科学与数学中，算法的核心特征包括有穷性、确切性、输入、输出和可行性。

三、oj题引进

在讲了这么多“官方”的叙述之后，你是不是还是觉得迷迷糊糊的呢？不要慌，有一句老话都说：光说不练假把式，先让我们来看一道oj习题。

怎么样？看完这道习题，你是否感到有点熟悉而又陌生呢？这时候就有人提问：up up这道题我好像看过，不就是和你之前写的字符串左旋（有需要请自行翻看）差不多吗？结果又真的是如此吗？咱们先抛开字符串左旋这个问题不谈，就单独看这道题，大家又有什么想法没有呢？
up呢给大家准备了三种方法，看看大家能不能仔细揣摩，如下：
法一：暴力解决法：

画图展示

我们通过代码编写和和画图感觉都没有太大的问题，那我们直接提交代码看结果：

宝子们，此刻的你是否又懵逼了？它给咱们说超出时间限制，那什么又是时间限制呢？或许有些宝子们可能是觉得自己没问题，是这个软件出了问题，就是不服气想再用其他的解法来尝试一下。好！那就让我们继续。
法二、再创数组法

画图展示：

欧克，直接提交代码：

这一次果然不出所料成功通过了，但是我对我刚刚的方法已经有了严重的怀疑——难道真的是我写错了吗？大家先别急，我们再试一试最后一种方法。
法三、多重逆置法

画图展示：

第三种方法也是通过了。现在你是彻底懵逼了吧？不着急，让你懵逼正是我今天的目的。现在我们继续回到刚刚那个问题:什么是时间限制?请大家带着探索求知的心态继续往下看。

四、复杂度

4.1复杂度的概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。
在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的
迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

4.2大O渐进表示法

在计算时间复杂度和空间复杂度的时候都需要用到大O渐进表示法：
1、时间复杂度和空间复杂度函数值T(N)中，只需要保留最高阶项，去掉低阶项，因为当N越来越大以至于趋近于无穷时，低阶项对T(N)整体结果的影响已经越来越小甚至忽略不计了。
2、如果最高阶项存在系数，则去掉这个高阶项的系数，因为到N不断变大以至于趋近无穷时，系数对T(N)整体结果的影响也越来越小甚至忽略不计。
3、如果T(N)没有任何与N相关的项，只有常数项，那就用常数1来代替所以常数项的和。

4.3时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？
1、因为程序运⾏时间和编译环境和运行机器的配置都有关系，比如同⼀个算法程序，⽤⼀个老编译器进行编译和新编译器编译，在同样机器下运⾏时间不同。
2、 同⼀个算法程序，用一个老低配置机器和新⾼配置机器，运⾏时间也不同。
3、并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。
那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执行次数。通过c语言编译链接章节学习，我们知道算法程序被编译后生成二进制指令，程序运行，就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)，假设每句指令执行时间基本⼀样(实际中有差别，但是微乎其微)，那么执行次数和运行时间就是等比正相关，
这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决⼀个问题的
算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b。

4.4时间复杂度计算示例

4.4.1示例1

4.4.2示例2

4.4.3示例3

4.4.4示例4

4.4.5示例5

在示例5 我们会发现有时候算法的复杂度存在最好、平均、最坏情况。
最坏情况：任意输入规模的最大运行次数（上界）；
平均情况：任意输入规模的期望运行次数；
最好情况：任意输入规模的最小运行次数（下界）。

4.4.6示例6

4.4.7示例7

注意：注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰
当n接近无穷大时，底数的大小对结果影响不大。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表示为 log n
不同书籍的表示方式不同，以上写法差别不大，我们建议使⽤ log n。

4.4.8示例8

注意：计算阶乘的时间复杂度=调用一次函数的时间复杂度*阶乘次数
T(N) = 1*N=N;
所以上面Fac的时间复杂度为 O(N)。

4.5空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象大小差异不会很⼤，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表示法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

4.6空间复杂度示例

4.6.1示例1

因为BubbleSort额外申请的空间只有exchange、i(有限个)局部变量，所以BubbleSort的空间复杂度为O(1).

4.6.2示例2

计算阶乘的空间复杂度 = 一次阶乘的空间复杂度*阶乘次数
因为Fac函数调用了N次，所以开辟了N个函数栈帧，而每次函数栈帧的空间复杂度为1，所以Fac的空间复杂度为 O(N)。

4.7常见复杂度对比

五、再回oj

ok啊兄弟们，关于数据结构与算法所有复杂度的知识我就给大家介绍完毕了。那让我们再回到我们之前抛出的oj题，

原来题目的下面是有要求的：
1、整个数组的元素个数为1—10的五次方；
2、每个元素的大小为**-2的31次方—2的31次方减1；**
3、旋转的次数为0—10的五次方。
法一（循环k次将数组所有元素向后移动一位）：时间复杂度O(N^2),时间复杂度太大，所以不通过

法二(开辟新的数组空间，先把要旋转的k个元素放入新数组，再把剩下的元素放入新数组，最后再整体返还给原数组)、时间复杂度为O(N)。本质是以空间换取时间

法三、(先逆置前k个元素，再逆置后 numsSize-k个元素，最后整体逆置)

相信到这里各位宝子们已经大彻大悟了，原来到最后既然是复杂度的问题。通过本次的案例分析，那我们以后写代码的时候也是不是也应该尽量减小我们代码的复杂度呢？

六、赠言

每个人都会犯错，但是我们需要做的是：找到错误、承认错误、改正错误。