《python算法教程》Day1- 渐近表示法渐近表示法的表示符号渐近表示法的使用方式典型的渐近类型及其算法复杂度优先级

算法的时间复杂度一般使用渐近表示法表示。

渐近表示法的表示符号

使用的符号主要有这三个:Of(n))Ω(f(n))���θ(f(n))��。分别表示时间复杂度不超过某个代表运行时间上界的函数f(n)的一系列函数、不低某个表示运行时间下限的函数f(n)的一系列函数、时间复杂度在时间复杂度上界函数f1(n)和时间复杂度下限函数f2(n)之间的一系列函数。 其中,f(n)f1(n)f2(n)定义为输入规模为n的函数

渐近表示法的使用方式

一般而言,表示运行时间的函数的形式多样,但渐近表示法中的函数仅截取函数中的主体部分,函数中用于加、减、乘的常数会被去掉。

典型的渐近类型及其算法复杂度优先级

以下为常见的渐近表示方式及复杂度的优先级。其中,复杂度由上往下逐渐增加。

θ(1):常数级 θ(log(n)):对数级 θ(n):线性级 θ(nlog(n)):对数线性级 θ(n^2):平方级 θ(n^3):立方级 O(n^k):多项式级 Ω(k^n):指数级 θ(n!):阶乘级

一般而言,算法的时间复杂度在多项式级或以下的问题有解,而从指数级开始,算法复杂度在这些范围的问题无解。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏蜉蝣禅修之道

LeetCode之Jump Game II

1614
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-分数查等级程序

Java案例-分数查等级程序 给定一个百分制的分数,输出相应的等级。 90分以上 A级 80~89 B级 70~79 C级 ...

3908
来自专栏数据结构与算法

UVA - 11178 Morley's Theorem

按照刘汝佳老师说的,这道题本身没有什么算法可言, 主要是考察选手对于几何算法的应用, 我们已经知道了点A,B,C 如果要求点D的话 我们可以先求出向量C-B的坐...

35613
来自专栏Leetcode名企之路

【Leetcode】53. 最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例:

983
来自专栏木子昭的博客

机器学习三剑客之NumpyNumpy计算(重要)

NumPy是Python语言的一个扩充程序库。支持高级大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。Numpy内部解除了Python的PI...

3636
来自专栏ATYUN订阅号

NumPy中einsum的基本介绍

einsum函数是NumPy的中最有用的函数之一。由于其强大的表现力和智能循环,它在速度和内存效率方面通常可以超越我们常见的array函数。但缺点是,可能需要一...

5073
来自专栏机器学习和数学

[ Tensorflow]Tensorflow Reduction operations

reduce系列在平时工程中是经常使用的,其中reduce_sum是使用最频繁的一个。主要用在计算loss的时候,当我们定义好loss之后,我们一般要求loss...

3614
来自专栏数据结构与算法

洛谷T21776 子序列

题目描述 你有一个长度为 nn 的数列 ,这个数列由 0,10,1 组成,进行 mm 个的操作: 1~l~r1 l r :把数列区间 [l, r][l,r] ...

3928
来自专栏海天一树

按出现次数从少到多的顺序输出数组中的字符串

问题 有一个数组为{"Liu Yi", "Chen Er", "Zhang San", "Chen Er", "Chen Er", "Li Si", "Li S...

2716
来自专栏算法修养

区间DP总结

做了几题区间动态规划的题目,觉得区间动态规划的题目是有点难的。区间DP大概是这一类的动态规划,在一个线性的数据上对区间进行状态转移,dp[i][j]表示i到j的...

2794

扫码关注云+社区

领取腾讯云代金券