这是什么代码的正确的大O

我想学习大O符号，我使用本C有点糊涂++代码：这是什么代码的正确的大O

void enterElements(int *s1, int s1Size) 
{ 
    for(int x = 0;x < s1Size;++x) 
    { 
    retry: 
     cout<<"Element "<<x + 1<<": "; 
     cin>>s1[x]; 
     int valid = validation(); 
     if(valid == 1) 
     { 
      cout<<"The input must be numbers."<<endl; 
      goto retry; 
     } 
    } 
}

因为我不知道该怎么做以及我得到3个结果：

9N + 1 - > O（N）
为7nm + 2M + 2N + 1 - > O（nm）的
7N^2 + 4N + 1 - > 0 （n^2）

这些是否正确？如果没有，你能帮我找到正确的答案吗？

int validation() 
{ 
int validation = 0; 
if(cin.fail()) 
{ 
    validation = 1; 
    cin.clear(); 
    cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n'); 
} 
else 
    validation = 0; 
return validation; 
}

来源

2013-05-12 evlvai

什么是'validation（）'？ – FDinoff 2013-05-12 22:32:07

如果'validation'是'return 1;'，你有'O（infinity）'。 – 2013-05-12 22:32:40

一个函数让我编辑它 – evlvai 2013-05-12 22:33:45

因为它可以利用用户输入也可以是从O（n）的任何东西无穷大（超过:-)）

来源

2013-05-12 22:35:12

最坏的情况：永远不会结束（没有人告诉你如何验证事情）

最佳状态：O（N）（如果你知道如何验证）

来源

2013-05-12 22:36:20

说最好的情况是最坏的情况（这是O（）符号的含义 - 这是一个上限）并不真实， – lollercoaster 2013-05-12 22:50:36

大哦符号确实不是很适用在这里。你所拥有的只是一个下界，绝对没有验证（）的保证，因此唯一的Big-Oh指定是O（inf），但是这非常没有帮助。

你的代码（应该都去验证正确），将是：

Ω(s1Size)

，因为它会被执行s1Size倍，而不是更少。 Big-Oh符号不适用于下限。因为我们无法保证goto语句将被使用多少次，因此没有上限，所以没有适用的Big-Oh推导。

您的运行时，简单来说：大于或等于s1Size迭代（禁止导致您的循环退出的错误）。

因此，最好的情况是上述情况，最糟糕的情况是，永远！

编辑：Ω在这里是正确的，而不是ω，因为Ω意味着运行时间大于或等于s1Size

来源

2013-05-12 22:39:09 lollercoaster

这是什么代码的正确的大O

回答

相关问题