c++ - 此代码的正确大 O 是什么

Question

我正在尝试学习 Big O 表示法，但我对这个 C++ 代码有点困惑：

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 个结果：

1. 9n + 1 -> O(n)
2. 7nm + 2m + 2n + 1 -> O(nm)
3. 7n^2 + 4n + 1 -> O(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;
}

Answer 1

大哦符号在这里真的不是很适用。您所拥有的只是一个下限，validation() 绝对没有保证，因此唯一的 Big-Oh 指定将是 O(inf)，但这非常无益。

您的代码（如果所有验证正常）将是：

Ω(s1Size)

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

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

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

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

Answer 2

鉴于它可以接受用户输入，它可以是从 O(n) 到无穷大（甚至更远:-) 的任何东西

Answer 3

最坏的情况：永无止境（没有人告诉你如何验证一件事）

最佳条件：O(n)（如果你知道如何验证）