核心内容摘要
夏日闷骚小班2.0：解锁你的另一面，让热情悄然绽放
什么是数据结构数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在⼀种或多种特定关系的数据集合。
不存在一种通用的数据结构针对于所有应用场景所以产生了多种多样的数据结构来适配不同的环境例如顺序表、链表、堆栈、二叉树、队列等
算法算法(Algorithim)是定义良好的计算过程指的是针对一个或一组输出经过该算法后产生一个或着多个输出的中间过程。
而评判算法优劣的其中一个因素就是时间复杂度和空间复杂度以力扣189旋转数组为例给定了一个需要右旋的数组以及右旋的次数最简单的方法即是将最后一个下标的元素取出放入中间变量tmp其余元素依次右移一个下标共循环k次即可。
根据思路写出代码void rotate(int* nums, int numsSize, int k) {int i 0;for(i0;ik;i)//每次往右挪一个数循环k次。
{int tmp nums[numsSize-1];int j 0;for(jnumsSize-1;j0;j--){nums[j]nums[j-1];}nums[0]tmp;}}运行可以发现两个测试用例可以通过但是提交却发现检查代码发现没有出现死循环的情况 那应该确实是代码运行时间超出了系统规定的时间。
根据此案例引出今天的主题——时间复杂度和空间复杂度
复杂度在代码写好后运行则需要消耗时间资源和空间(内存)资源因此衡量一个算法的好坏是根据时间和空间来衡量的
1时间复杂度在计算机科学中定义时间复杂度为函数式T(N)。
它描述的是算法的运行时间随变量不同而发生变化的一种趋势它并不是实际的运行时间而是一种趋势。
要理解清楚它不是具体的某个值而是一种趋势。
首先提出表示时间复杂度的方法然后根据具体
案例分析如何应用这个方法计算时间复杂度表示时间复杂度的方法为大O渐进法。
其具体规则为
时间复杂度函数式T(N)中只保留最高阶项去掉那些低阶项因为当N不断变大时低阶项对结果影响越来越⼩当N无穷大时就可以忽略不计了。
如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数对结果影响越来越小当N无穷大时就可以忽略不计了。
T(N)中如果没有N相关的项⽬只有常数项用常数1取代所有加法常数。
接下来结合具体代码案例并应用上述的三个规则来计算时间复杂度void Func1(int N){int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);}首先看这个代码的for循环中出现了变量Nwhile循环中虽然也出现了变量M但其为定值循环10次大致可以写为O(N
而根据第一条规则只保留高阶项最后答案是O(N)。
再来看第二个例子void Func2(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);}这段代码定义了两个变量N和M又进行了两个for循环分别循环N次和M次所以其时间复杂度为O(MN)如果MNN就可以忽略不计O(M)同理如果NMM忽略不计O(N)。
void Func3(int N) {int count 0;for (int k 0; k 100; k) {count;}printf(%d\n, count);}在Fun3这个函数例子中并没有出现关于N变量的循环等操作所以其时间复杂度为一个常数而对于常数根据第三条规则将其写作O(
。
const char* strchr(const char* str, int character) {const char* p_begin s;while (*p_begin ! character) {if (*p_begin \
return NULL;p_begin;}return p_begin;}对于strchr这个函数仔细观看出现的while循环则会发现它的时间复杂度取决于这个while循环而while循环中似乎不是一个可以明确说出循环多少次的变量是根据要查找的character有关。
运气好的话第一个是时间复杂度为O(
运气不好的话最后一个是其时间复杂度为字符串的长度O(N)但 O(N)也就是最坏的情况了如果最坏情怀下都能满足要求那其它情况肯定能满足要求。
所以对于分类讨论的情况就按照最坏的情况。
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
break;}}这段代码的特点是外层循环和内层循环的次数不相同随着循环次数的变化内层循环的次数也会发生相应变化 。
先尝试枚举 格式如下 (外层)第n次(内层)循环x次 。
第一次n-1第二次n-2第三次n-3 ------第n-1次1 。
把总循环次数加起来则为可看出是等差数列求和则为 根据大O渐进法第二条规则时间复杂度为O(N^
。
void func5(int n) {int cnt 1;while (cnt n) {cnt * 2;}}fun5这段代码较为简单while循环的终止条件是n内部则为每次×2相当于数出来需要2的多少次相乘就会大于n其实就是对数函数的形式。
而当n接近无穷大时对数函数的底数对于其影响并不大所以在表示时间复杂度时都将其统一写成。
long long Fac(size_t N) {if (N
return 1;return Fac(N -
* N;}最后考虑到递归的情况递归的时间复杂度 单次时间复杂度*递归次数。
对于上述阶乘递归单次时间复杂度为1共递归n次最后时间复杂度为O(n)。
2空间复杂度空间复杂度的定义为在一个运算执行的过程中有多少额外开辟的空间。
计算规则也是大O渐进法的三条规。
函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因 此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。
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
break;}}例如这段代码 在函数运行过程中额外开辟的空间只有int exchange 和size_t 为常数所以空间复杂度为O(
。
而对于fun5的递归来说空间复杂度 单次运行的空间复杂度* 递归次数单次递归的空间复杂度为O(
共有n次所以总的空间复杂度为O(N);下述是两张常见复杂度的图再次回到开头的题目实例如果用依次向后移动的方法其时间复杂度为O(N^
而题目中提供的元素个数最多为10^5总时间为10^10ms相当于10^7s会超过时间限制。
下述提供两种可通过的解题思路