如何判断时间复杂度的级别

简介: 如何判断时间复杂度的级别

首先来说一下什么是时间复杂度:

(来源于百度百科)在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。


那如何判断时间复杂度是大是小呢?

时间复杂度的排序是O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)。


那如何知道时间复杂度是哪一个级别的呢?

首先说O(1),这说明代码没有运行全部的代码,也没有循环查找,而是直接找到了自己需要的东西,例如,查找一行数据里的第五个数据,直接给出存储地址,不需要一个一个的取对比,直接去指定位置拿取数据的时间复杂度就是O(1)。


O(n)的复杂度就是有一个for循环,循环查找一个表里的内容,找到需要的内容后返回结果。如下图:



O(n^2)就是嵌套for循环,在for循环里在嵌套一个for循环,里边的循环全部循环一次,外边的循环循环一次,接着里边的循环在循环一次,是不是相当于运行了n*n次,如下图:




对数阶O(log n)通常是递归,一般情况下,用了递归的算法的时间复杂度,一般为O(log n)。


声明,这些算法是对时间复杂度的一个估值,不是确定的,但是这确实是对代码质量的一个衡量标准。


一般常见的时间复杂度需要的也就这几样,其它的复杂度对应在代码里的目前博主也不知道,如果哪天学会了,会再来更新本章博客的。


相关文章
|
3月前
最小操作次数问题
最小操作次数问题
33 1
|
3月前
|
算法 测试技术 C#
C++二分查找算法:包含每个查询的最小区间
C++二分查找算法:包含每个查询的最小区间
|
3月前
|
Java
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
51 0
|
2月前
39.组合总和(回溯)
39.组合总和(回溯)
|
3月前
|
算法 测试技术 C++
【动态规划】【C++算法】801. 使序列递增的最小交换次数
【动态规划】【C++算法】801. 使序列递增的最小交换次数
|
8月前
|
算法 测试技术 C#
C++二分算法:得到山形数组的最少删除次数
C++二分算法:得到山形数组的最少删除次数
|
8月前
|
算法 测试技术 C#
C++算法: 最大化数组末位元素的最少操作次数
C++算法: 最大化数组末位元素的最少操作次数
|
Cloud Native Go
801. 使序列递增的最小交换次数:动态规划
这是 力扣上的 801. 使序列递增的最小交换次数,难度为 困难。
|
存储 算法 C语言
【二分查找】2080. 区间内查询数字的频率
二分查找是一种高效的查找算法,其时间复杂度为 O(log n)。在许多情况下,我们需要在一个有序数组中找到某个目标值的搜索范围。本文将介绍一种基于二分查找的搜索范围查找算法,该算法能够快速找到目标值在数组中的起始和结束位置。
106 0