时间复杂度的五个记号

简介: 时间复杂度的五个记号

算法复杂度分析中的符号(Θ、Ο、ο、Ω、ω)

**

首先要明白两个复杂度:

一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。

Θ,既是上界也是下界(tight),就是相等,准确的复杂度

Ο,表示渐进上界(tightness unknown),小于等于的意思,近似复杂度。

ο,表示上界(not tight),小于的意思,明确的知道小于它,准确计算出来的。

Ω,表示渐进下界(tightness unknown),大于等于的意思,近似复杂度。

ω,表示下界(not tight),大于的意思,明确的知道大于它,准确计算出来的。

20200322135521493.png


顺便补充:

几种常见的复杂度关系

20200322135225496.png

n默认为2,n因为计算机中很多程序是用二分法实现的。

相关文章
|
5月前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
5月前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
11月前
|
机器学习/深度学习 算法
算法分析 | 第三套(渐近符号)
算法分析 | 第三套(渐近符号)
96 0
|
11月前
|
机器学习/深度学习 算法
算法分析 | 小 o 和小欧米茄符号
算法分析 | 小 o 和小欧米茄符号
188 0
|
11月前
|
算法 测试技术 C#
C++字典树算法:找出强数对的最大异或值 II
C++字典树算法:找出强数对的最大异或值 II
|
机器学习/深度学习 Go C语言
921. 使括号有效的最少添加:简单贪心思想
这是 力扣上的 921. 使括号有效的最少添加,难度为 中等。
|
机器学习/深度学习 算法 测试技术
686. 重复叠加字符串匹配 :「卡常」&「上下界性质」&「KMP」&「字符串哈希」
686. 重复叠加字符串匹配 :「卡常」&「上下界性质」&「KMP」&「字符串哈希」
|
机器学习/深度学习
318. 最大单词长度乘积 : 简单位运算模拟题
318. 最大单词长度乘积 : 简单位运算模拟题
|
机器学习/深度学习 算法 索引
【字符串】最长回文子串 ( 蛮力算法 )
【字符串】最长回文子串 ( 蛮力算法 )
100 0
【字符串】最长回文子串 ( 蛮力算法 )