首页 > 试题广场 >

分析下面函数的时间复杂度。 void func(in

[问答题]
分析下面函数的时间复杂度。
void  func(int  n)
{
    int  i = 1, k = 100;
    while ( i < n)
{
    k++;
    i += 2;
}
}

循环n次,时间复杂度为o(n),常数忽略

发表于 2019-08-23 10:40:55 回复(0)
void  func(int  n)
{
    int  i = 1, k = 100;//1
    while ( i < n)//2
    {
       k++;//3
       i += 2;//4
    }
}
  • 语句1的频度为1
  • 语句2的频度为n/2
  • 语句3的频度为n/2
  • 语句4的频度为n/2
  • T(n)=1+n/2+n/2+n/2=3n/2+1=O(n).
发表于 2020-05-03 20:01:23 回复(0)
k++语句执行了n/2次,所以时间负责度为O(n)
发表于 2021-07-09 22:35:17 回复(0)
O(n)
发表于 2020-02-10 03:57:18 回复(0)
O(n)?
发表于 2020-01-04 10:21:44 回复(0)

log2n

发表于 2019-11-27 01:12:16 回复(0)
1
发表于 2019-07-29 12:01:18 回复(0)