delphi 做直播网站,东莞部门网站建设,电商是做什么工作的,笑话类网站 源代码数学基础
设f和g是定义域为自然数集N上的函数
存在正整数c、n#xff0c;使0f(n)cg(n)成立#xff0c;称f(n)的渐进上界是g(n)#xff0c;记作f(n)O(g(n))存在正整数c、n#xff0c;使0cg(n)f(n)成立#xff0c;则称f(n)渐进下界是g(n)#xff0c;记作…数学基础
设f和g是定义域为自然数集N上的函数
存在正整数c、n使0f(n)cg(n)成立称f(n)的渐进上界是g(n)记作f(n)O(g(n))存在正整数c、n使0cg(n)f(n)成立则称f(n)渐进下界是g(n)记作f(n)Ω(g(n))若f(n)O(g(n))且f(n)Ω(g(n))则称f(n)与g(n)同阶记作f(n)Θ(g(n))
常见阶从大到小的顺序
O(n) O(nlogn)O(n^2)O(2 ^n)O(n!)O(n ^n)
∑1kΘ(logn)\sum \frac{1}{k} \Theta (logn)∑k1Θ(logn) lognlognΘ(nloglogn)logn^{logn} \Theta (n^{loglogn})lognlognΘ(nloglogn) log(n!)Θ(nlogn)log(n!) \Theta (nlogn)log(n!)Θ(nlogn)
求解递推方程的方法
许多递推方程不能求出精确的解但通过可以估计函数的阶来估计时间复杂度 1迭代法 所谓迭代就是从原始递推方程开始代入值直到得到初值然后将结果简化
2递归树 设T(n)aT(n/b)f(n)以f(n)为节点值迭代构建递归树直到函数中不在包含T(n)函数复杂度为递归树每层值的和 3主定理
