一篇文章教会你算法复杂度(内附详细案例+实战)

一篇文章教会你算法复杂度(内附详细案例+实战)算法在编写成可执 程序后 运 时需要耗费时间资源和空间 内存 资源

大家好,欢迎来到IT知识分享网。

复杂度的概念

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

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

时间复杂度

定义:在计算机科学中,算法的时间复杂度是⼀个函数式T(N),它定量描述了该算法的运⾏时间。时 间复杂度是衡量程序的时间效率,那么为什么不去计算程序的运⾏时间呢?

  1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系,⽐如同⼀个算法程序,⽤⼀个⽼编译 器进⾏编译和新编译器编译,在同样机器下运⾏时间不同。
  2.  同⼀个算法程序,⽤⼀个⽼低配置机器和新⾼配置机器,运⾏时间也不同。
  3. 并且时间只能程序写好后测试,不能写程序前通过理论思想计算评估。

 一篇文章教会你算法复杂度(内附详细案例+实战)

空间复杂度 

空间复杂度也是⼀个数学表达式,是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。 空间复杂度不是程序占⽤了多少bytes的空间,因为常规情况每个对象⼤⼩差异不会很⼤,所以空间复 杂度算的是变量的个数

注意:函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好 了,因 此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

⼤O的渐进表⽰法 

我们只需要计算程序能代表增⻓量 级的⼤概执⾏次数,复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

⼤O符号(Big O notation):是⽤于描述函数渐进⾏为的数学符号

计算时间复杂度

推导⼤O阶规则

注意:对计算机运行效率来说,执行次数亿、万、1并无差别

  • 时间复杂度函数式T(N)中,只保留最⾼阶项,去掉那些低阶项,因为当N不断变⼤时, 低阶项对结果影响越来越⼩,当N⽆穷⼤时,就可以忽略不计了。示例:

一篇文章教会你算法复杂度(内附详细案例+实战)

一篇文章教会你算法复杂度(内附详细案例+实战)

  • 如果最⾼阶项存在且不是1,则去除这个项⽬的常数系数,因为当N不断变⼤,这个系数 对结果影响越来越⼩,当N⽆穷⼤时,就可以忽略不计了。 

一篇文章教会你算法复杂度(内附详细案例+实战)

  • T(N)中如果没有N相关的项⽬,只有常数项,⽤常数1取代所有加法常数。  

一篇文章教会你算法复杂度(内附详细案例+实战)

特殊情况 

有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况:任意输⼊规模的最⼤运⾏次数(上界)

平均情况:任意输⼊规模的期望运⾏次数

最好情况:任意输⼊规模的最⼩运⾏次数(下界)

⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界,也就是最坏运⾏情况。 

一篇文章教会你算法复杂度(内附详细案例+实战)

冒泡排序的复杂度计算 

一篇文章教会你算法复杂度(内附详细案例+实战)注意!!!内循环有误:i = 1,应为n-1 n-2…….1 0共n个数  

关于对数(log n)的复杂度 

一篇文章教会你算法复杂度(内附详细案例+实战)

注意: 

  1.  文章中 log2 n 、 log n 、 lg n 的表⽰
  2.  当n接近⽆穷⼤时,底数的⼤⼩对结果影响不⼤。
  3.  因此,⼀般情况下不管底数是多少都可以省略不 写,即可以表⽰为 log n 不同书籍的表⽰     ⽅式不同,以上写法差别不⼤,建议使⽤ log n

递归的时间复杂度 

(单次递归的时间复杂度 * 递归次数)

一篇文章教会你算法复杂度(内附详细案例+实战)

计算空间复杂度 

 空间复杂度计算规则基本跟时间复杂度类似

注意!!!:函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好 了,因 此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

冒泡排序的空间复杂度

一篇文章教会你算法复杂度(内附详细案例+实战)

递归的空间复杂度 

一篇文章教会你算法复杂度(内附详细案例+实战)

复杂度算法题(实战演练)

旋转数组

. – 力扣(LeetCode)

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 

输入: nums = [1,2,3,4,5,6,7], k = 3 输出:
[5,6,7,1,2,3,4]
解释: 向右轮转 1 步:
[7,1,2,3,4,5,6]
向右轮转 2 步:
[6,7,1,2,3,4,5]
向右轮转 3 步:
[5,6,7,1,2,3,4] 

示例 2:

输入:nums = [-1,-100,3,99], k = 2 输出:[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]

提示:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

思路1

空间复杂度 O(1)

 时间复杂度 O(n^2 ) 

循环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: 

空间复杂度 O(n)

时间复杂度 O(n )

申请新数组以空间换时间

申请新数组空间,先将后k个数据放到新数组中,再将剩下的数据挪到新数组中 

void rotate(int* nums, int numsSize, int k) { int newArr[numsSize]; for (int i = 0; i < numsSize; ++i) { newArr[(i + k) % numsSize] = nums[i]; } for (int i = 0; i < numsSize; ++i) { nums[i] = newArr[i]; } }

一篇文章教会你算法复杂度(内附详细案例+实战)

 思路3:(涉及双指针)

空间复杂度 O(1)

时间复杂度 O(n )

前n-k个逆置: 4 3 2 1 5 6 7 

后k个逆置 :4 3 2 1 7 6 5

整体逆置 : 5 6 7 1 2 3 4 

运行机制:

                               一篇文章教会你算法复杂度(内附详细案例+实战)

void reverse(int* nums,int begin,int end) { while(begin<end){ int tmp = nums[begin]; nums[begin] = nums[end]; nums[end] = tmp; begin++; end--; } } void rotate(int* nums, int numsSize, int k) { k = k%numsSize; reverse(nums,0,numsSize-k-1); reverse(nums,numsSize-k,numsSize-1); reverse(nums,0,numsSize-1); }

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/126960.html

(0)
上一篇 2025-09-14 18:10
下一篇 2025-09-14 18:15

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信