算法的时间复杂度的定义中常数C是什么?

码强
  • 26

案例

我们假设计算机运行一行基础代码需要执行一次运算。

int aFunc(void) {
    printf("Hello, World!\n");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

那么上面这个方法需要执行 2 次运算

int aFunc(int n) {
    for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

这个方法需要 (n + 1 + n + 1) = 2n + 2 次运算。
我们把 算法需要执行的运算次数 用 输入大小n 的函数 表示,即 T(n) 。
此时为了 估算算法需要的运行时间 和 简化算法分析,我们引入时间复杂度的概念。
定义:存在常数 c 和函数 f(N),使得当 N >= c 时 T(N) <= f(N),表示为 T(n) = O(f(n)) 。

问题

请问:

存在常数 c 和函数 f(N),使得当 N >= c 时 T(N) <= f(N),表示为 T(n) = O(f(n)) 。

这里这句话是什么意思?

还有这里的这个C是什么? 指的是第2n + 2 还是2?

如果是 2n+2的话,则C代表的该函数总共运行的次数, 对吗? 那这里的常数C值得就是函数总运行次数对吗?

请不吝赐教.

回复
阅读 2.3k
2 个回答
代码宇宙
  • 15.6k

都不是。既不是2n+2也不是2。

c大概是这么一个意思:对于不等式n^2>=100n,得到的最小解就是c

belingud
  • 1
新手上路,请多包涵

这是一个数学问题,C代表任意一个数,类似于函数的变量int n,定义时不能指定是多少,c只是定义一个数学函数的概念,可以理解为C无穷大你不能计算的时候,只能用一个式子,来表示x=c时,f(x)的值。
比如说,(1,1),(2,2),(3,3)...表示的直线,当x>c的时候,c为一个常数,即c为任意一个数,f(x)=x。当表示时间复杂度时,T(n)表示为,函数运行次数多项式,的最高项,去掉系数。也去掉了这个不确定的c。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏