算法实际时间复杂度例题

1. 算法题时间复杂度问题

在算法题中调用内置函数应该考虑把这个函数算入总复杂度中的。调用内置函数，与调用自定义函数的实质是一样的。如果在一个本身时间复杂度为O(n)在算法中调用了一个时间复杂度为O(logn)的内置函数，那么，整个算法的时间复杂度就是O(nlogn)

2. 算法的时间复杂度计算问题

第一题:
int
i=1,k=100这条语句算法步数是2步，执行频率是1;
循环中，
k=k+1;这条语句每次算法步数是1;执行频率是n/2-1;
i+=2这条语句每次算法步数是1;执行频率是n/2-1;
所以算法复杂度为1*(n/2-1)+1*(n/2-1)+2=n=o(n);

3. 算法时间复杂度x=2 while(x<n/2) x=2*x 求算法时间复杂度

算法时间复杂度为：O（log₂n）。

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作：S（n）＝O（f（n））。

算法执行期间所需要的存储空间包括3个部分：算法程序所占的空间；输入的初始数据所占的存储空间；算法执行过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

4. 算法设计题:计算时间复杂度

关于时间复杂度的计算是按照运算次数来进行的，比如1题：
sum1(intn)
{intp=1,sum=0,m;//1次
for(m=1;m<=n;m++)//n+1次
{p*=m;//n次
sum+=p;}//n次
return(sum);//1次
}
最后总的次数为
1+（n+1）+n+n+1+1=3n+3
所以时间复杂度f（o）=n；（时间复杂度只管n的最高次方，不管他的系数和表达式中的常量）
其余的一样，不明白的可以来问我

5. 算法时间复杂度问题，题目如下，谢谢！

楼主你好
大致是这样:
首先说:
for(i=1;i<=n;i*=2)
语句;
这个的循环的执行的次数
是:
og2 (n-1 +1)
log以2为底 n的对数 + 1

那么把 i=1换做j j是从1~n-1 因为 当j为n时函数结束

因此运行的次数就是：
j:1~n-1
(log2 (n-j+1))+1 的和
就是:
log2 (n!) +n

希望能帮助你哈

6. 分析下列算法的时间复杂度。麻烦也告诉一下怎样算的，谢谢！

每当调用这个函数时会产生2个递归分支，所以时间复杂度是O(2^n)。
n==1时，调用1次rec(1)，
n==2时，调用1次rec(2)，2次rec(1)，
n==3时，调用1次rec(3)，2次rec(2)，4次rec(1)，
以此类推，总的调用次数为2^0+2^1+2^2+...+2^(n-1)=2^n-1，
因为函数内不存在循环，T(n)=(2^n-1)*1=2^n-1，
存在正的常数c,n0使得对于任意n>=n0时有T(n)<=c*2^n，
所以这个时间复杂度是O(2^n)。

7. 算法时间复杂度的计算例题

第一题：
int i=1,k=100这条语句算法步数是2步,执行频率是1；
循环中, k=k+1;这条语句每次算法步数是1；执行频率是n/2-1; i+=2这条语句每次算法步数是1；执行频率是n/2-1;
所以算法复杂度为1*（n/2-1）+1*（n/2-1）+2=n=o(n);