计算时间复杂度（连续循环）

对于下面的代码：计算时间复杂度（连续循环）

int func(int x, int y) 
{ 
    int flag=0; 

    for(flag=0; flag<x; flag++) 
    { 
     .... 
    } 

    for(flag=0; flag<y; flag++) 
    { 
     .... 
    } 

    return 0; 
}

以下情况的时间复杂度（我的理解）是 -

x > y => O(x+y) 
y < x => O(x+y) 
x = y => O(2x)

有人可以验证，如果我是正确的？

谢谢。

来源

2010-12-17 Gong

欢迎来到Stack Overflow！只要你知道，这里的问题和答案可以格式化，看起来更好，更易于阅读。您应该在这里阅读格式规则，以便您可以设置代码片段的格式：http://stackoverflow.com/editing-help – 2010-12-17 03:43:39

实际上，由于您没有使用代码格式，因此“<”符号后的所有内容都是丢失。所以我们实际上看不到你的代码:( – 2010-12-17 03:44:30

你是对的.. – Enrique 2010-12-17 03:48:41

x> y => O（x + y） - 是的。但是，如果x = O（y），那么就是O（x）。

y < x => O（x + y） - 是的。以上同样的解释。

x = y => O（2x） - 不完全。您忽略了大O分析中的常数因素。这个想法是，当x变为无穷大时，'2'或常数将对函数的增长率作出很大贡献。 O（y^2） - 大O分析的另一个特点是你只考虑主要术语。

大O分析的一个很好的介绍可以在这里找到一个video讲座格式。查看大O分析的第二讲。

来源

2010-12-17 04:08:15

大O符号不使用常数乘数。即，没有O（2n），只有O（n）。这是相对于指数，它是经常可以看到O（2^N）等

你的函数是线性的，因此，如果x == y，然后量级被简单地列为O（X ）。

来源

2010-12-17 03:59:39 chrisaycock

计算时间复杂度（连续循环）

回答

相关问题