诸城网站开发,铜陵保障性住房和城乡建设网站,网络运营商自动选择,百度网站ip地址参考来源#xff1a; 维基百科#xff1a;https://en.wikipedia.org/wiki/Time_complexity
1 什么是时间复杂度#xff1f;
时间复杂度 定性描述了算法的运行时间。#xff08;并不是表示解决一个问题花了多少时间#xff0c;而是描述问题规模扩大与算法运行时间增加的…参考来源 维基百科https://en.wikipedia.org/wiki/Time_complexity
1 什么是时间复杂度
时间复杂度 定性描述了算法的运行时间。并不是表示解决一个问题花了多少时间而是描述问题规模扩大与算法运行时间增加的关系
常见的时间复杂度有
常数时间O(1)如访问数组中的单个元素
对数时间O(log n)如二分搜索
线性时间O(n)如对所有元素的求和
准线性时间O(nlogn)如快排算法
多项式时间 为常数
1.1 多项式时间
An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm.
1.1.1 强多项式时间和弱多项式时间
Strongly polynomial time is defined in the arithmetic model of computation. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if
the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; andthe space used by the algorithm is bounded by a polynomial in the size of the input.
An algorithm which runs in polynomial time but which is not strongly polynomial is said to run in weakly polynomial time.
强多项式时间算法时间复杂度不会因输入数据的大小改变而与输入数据的结构复杂度有关。
1.2 非多项式时间
1.2.1 指数时间
1.2.2 阶乘时间
1.2.3 伪多项式时间
算法的时间复杂度是关于输入数据的大小的多项式时间却是输入数据长度的指数时间。如素数的检测。
2 什么是问题
P所有可以由一个确定型图灵机在多项式时间内解决的问题。
2.1 NP
NP所有可以在多项式时间内验证它的解是否正确的问题/可以在非确定型图灵机上在多项式时间内解决的问题。
2.2 NPC
NP-Complete一个决定性问题A若是NPC则表示它对NP是完备的1、它是一个NP问题2、其他属于NP的问题都可以多项式时间内归约成它。
只要任意一个NPC问题找到了多项式时间算法那么NP问题都可以多项式时间内解决即PNP。但目前NPC大多只有指数或者阶乘复杂度的算法 or 伪多项式时间算法。
2.3 NPH
NP-HardA若是NP-Hard其他属于NP的问题都可以在多项式时间内归约成它。 2.4 NPC问题的相互推导 3 算法复杂性分析
3.1 时间复杂度
一般算法的每次运行输入不同带来的具体复杂度也不同因此考虑算法在最坏、最好、平均情况下的时间复杂度其中最坏复杂度比较有实践价值。
而对于类似3N^24NlogN7此类复杂度当时3N^2称为其渐进复杂性。因此可以看出比较两个算法效率时只要关心渐进复杂性的阶就可以引入渐进意义下的符号.
O存在常数C和自然数N_0使得NN_0时有f(N)Cg(N)则称f(N)在N充分大时有上界且g(N)是它的一个上界。f(N)O(g(n))
存在常数C和自然数N_0使得NN_0时有f(N)Cg(N)则称f(N)在N充分大时有下界且g(N)是它的一个下界。f(N)\Omega(g(n))
f(N)O(g(n)) f(N)\Omega(g(n)) 同阶
o给定任意都存在正整数N_0使得NN_0时有f(N)/g(N). 3.2 空间复杂度
