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

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

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

(来源于百度百科)在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大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)。


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


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


相关文章
|
7月前
最小操作次数问题
最小操作次数问题
48 1
|
7月前
|
算法 测试技术 C#
C++二分查找算法:包含每个查询的最小区间
C++二分查找算法:包含每个查询的最小区间
|
存储 C语言 C++
问题 D: DS查找—二叉树平衡因子(不一样的新做法哦)
问题 D: DS查找—二叉树平衡因子(不一样的新做法哦)
107 0
|
7月前
|
Java
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
69 0
|
6月前
39.组合总和(回溯)
39.组合总和(回溯)
|
算法 测试技术 C#
C++二分算法:得到山形数组的最少删除次数
C++二分算法:得到山形数组的最少删除次数
|
算法 C语言 C++
【模拟】特别数的和、移动距离、连号区间、错误票据思路详解及代码实现
取出最后一位,然后将n除去最后一位,将刚刚取出的进行判定。
84 0
算法学习--递归打印*到*的数
算法学习--递归打印*到*的数
|
前端开发 程序员
大量if else判断如何优化?@Valib详解
大量if else判断如何优化?@Valib详解
大量if else判断如何优化?@Valib详解
|
算法 Go
算法练习第十题——寻找重复数(不修改数组)
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。