时间复杂度推导

作者：Guff_9hys | 2024-07-17 21:37:27

踩

时间复杂度推导

时间复杂度的推导

前言
结论
实例
常用的时间复杂度表格

前言

在刚开始学习算法的时候，其实开篇老师就讲解了算法时间复杂度的推导，但那个时候自己不太注意所以一直没有搞明白。学到后面尤其是对于判断这个算法好不好的时候，经常会用到时间复杂度的推导，这也是能区分优秀程序员的重要本领之一，今天就梳理一遍时间复杂度的推导。

结论

时间复杂也就是大O阶的推导：（先由执行次数函数推导）
一.用常数1取代运行时间中的所有加法常数。
二.在修改后的运行次数函数中，只保留最高阶项。
三.得到的最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大0阶。(一定是保证最后大O阶的最高项的乘数为1)

实例

下面来看两个个实例帮你更加理解大O阶的推导与深入：
例一：
在这里插入图片描述
用我们推导大0阶的方法：
一.这里不存在加法常数所以不用考虑。
二.只保留最高阶项，这里的最高阶项是n²/2，所以保留。
三.去除掉这个相乘非1的常数，所以最后时间复杂度为O(n²)。
其实理解大0阶的推导并不难，有

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】