大O表示法例子

~

首先看一个简单的示例：

• int num1, num2;


• for(int i=0; i<n; i++){


• num1 += 1;


• for(int j=1; j<=n; j*=2）{


• num2 += num1;


• }


• }

分析：

语句int num1, num2;的频度为1次；

语句i=0;的频度为1次；

语句i<n; i++; num1+=1; j=1; 的频度为n次；

语句j<=n; j*=2; num2+=num1;的频度为n*log2n次；

T(n) = 2 + 4n + 3n*log2n

忽略常量和低次幂，只关注最高次幂的系数，我们得到：

f(n) = n*log2n

计算极限比值，当n趋于无穷大：

lim(T(n)/f(n)) = (2+4n+3n*log2n) / (n*log2n)

= 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3

当n趋于无穷，1/n和1/log2n趋于0，极限值为3。

因此，时间复杂度为：T(n) = O(n*log2n)

简化计算步骤：

1. 找出执行次数最多的语句，这里是num2 += num1


2. 计算语句执行次数的数量级，这里是n*log2n


3. 用大O表示法表示结果：T(n) = O(n*log2n)

补充说明：

最坏时间复杂度：考虑问题规模及输入实例对算法的影响。

数量级计算：用科学计数法表示，如5000=5x10³（log5000=3）。

求极限技巧：利用1/n的特性，n趋于无穷时，1/n趋于0。

大O表示法规则：

• 加法规则：T(n,m) = T1(n) + T2(n) = O(max(f(n),g(m)))


• 乘法规则：T(n,m) = T1(n) * T2(m) = O(f(n) * g(m))


• 常数乘法：T(n) = O(c * f(n)) = O(f(n))，c为常数


• 经验规则：复杂度与时间效率的关系

复杂情况分析：

• 并列循环：时间复杂度相加，如for循环的总复杂度为Ο(n2)


• 函数调用：只计算可运行语句，如printsum方法的优化，原复杂度为O(n)，优化后为O⑴

扩展资料

大O表示法：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

---

秀山土家族苗族自治县18620118975： 大o表示法 - 搜狗百科？
归晏安内：[答案] G(x)=1/√5*[ 1/(1-α*x)-1/(1-β*x) ]=1/√5*[ (α-β)*x+(α^2-β^2)*x+...+...] 原因: 1/(1-t)=1+t+t^2+t^3. 将t分别替换成α*x和β*x,对应项合并,就可推导出

秀山土家族苗族自治县18620118975： 数据结构 数量级怎么计算与表示 O代表什么 - ？
归晏安内： O可考虑为order的首字母缩写,相应有大O表示法.它们通常出现在程序设计与计算相关描述里面,把整个程序重复执行次数之和记为T(n),称为时间复杂度,其中n为求解问题涉及的数据个数或称为问题规模.当n足够大时,不同求解算法将会导致显著差异的T(n).为此,定义O()来描述T(n)的数量级,用以评估不同算法的效率.需要强调的是,时间复杂度T(n)一般并不对应真实的程序执行时间.

秀山土家族苗族自治县18620118975： 大O表示法的计算过程 - ？
归晏安内： 1和3本来就一样么..居然还有这么恶心的公式..c和n0是随便找的,只要能找到就行 最简单的判断复杂度的方法就是:对于任何表达式,先合并同类项,然后取含n的最高阶的项,去掉常数 比如2中,n的最高阶的项就是6*2^n,去掉常数就是2^n 一般地,排序算法最快是O(nlog2(n)),折半查找是O(log2(n))

秀山土家族苗族自治县18620118975： 谁能解释一下计算机中的数据结构中的“时间复杂度T(n)=O(f(n))”每个字母的含义? - ？
归晏安内：[答案] T(n)就是表示时间复杂度了 O是大O表示法(Big-O Notation),f(n)是大O表示法表示时间复杂度的结果.

秀山土家族苗族自治县18620118975： 设n为正整数,利用大“O”表示法,将下列程序段的执行时间表示为n的函数: - ？
归晏安内： x=1;y=1; for( i=0; i<n; j++)y++;因此总体为O(n^2)...

秀山土家族苗族自治县18620118975： 时间复杂度 T(n)=O(f(n)),的 O什么意思 - ？
归晏安内： O(n)这个大O表示的是最坏情况下的时间复杂度,就比如你举的例子,一共n^3次乘法和n^3次加法,那么加起来就是2*n^3.然后如果有一个表达式f(n),使得n趋于无穷大的时候,lim(2*n^3)/f(n)=常数c,那么就可以用大O表示.表示为O(f(n)),而且规定f(n)的表达式是不带常数的系数的,那么在这里f(n)=n^3.一般用大O表示算法复杂度只需要取次数最高的项,而且去掉系数就OK了,不用每次都这么算的.三重循环而且每重循环都执行n次的话直接O(n^3)就好了.

秀山土家族苗族自治县18620118975： 指出下面算法的时间复杂度?(用大O表示法) - ？
归晏安内： o(n^3)

秀山土家族苗族自治县18620118975： 无穷小符号是什么啊? - ？
归晏安内： 无穷小符号是用小写希腊字母表示,如α、β、ε等,有时候也用α(x)、ο(x)等,表示无穷小量是以x为自变量的函数.具体来说,当自变量x无限接近某个点或绝对值无限增大时,函数值f(x)与0无限接近,即f(x)→0或f(x)=0,则称f(x)为当x→x0或x→∞...

秀山土家族苗族自治县18620118975： 求时间复杂度,在线等,最好有公式推导. - ？
归晏安内： 一、概念 时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样:a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a ! =0时,时间复杂度就是O(2^n); a=0,b<>0 =>O(n^3); a,b=0,c<>0 =>O(n^2)...