1

编辑：到目前为止，我已经在 SO 上阅读了大约 3 个小时，但对我来说仍然没有多大意义（这意味着我在询问之前已经完成了研究）。忘记在OQ中说明了。

好吧，我对 BigO 完全不知所措，当我尝试将其他方法应用于我的代码时，这对我来说几乎没有意义。如果有人可以提供帮助，我想要一个如何计算以下 BigO 的演练。

int i = 0;
int t = 0;
while(i <= 4){
    // Basic instructions
    int s = 0;
    while(s <= 4){
        // Basic instructions
        t + 2;
        if(conditions){ // Checks if a value isn't in a hashset
            for(int r = 0; r <= t; r++){
                // Basic instructions
                if(conditions){ // This statement can make t equal to any number < t, checks if two strings are identical.
                    // Do stuff
                }else{
                    // Do stuff. 
                }
            }
        }else if(condition){
            i++;
        }
        s++;
    }
}

如果需要，我可以将完整的代码放在那里，但据我所知，我认为这应该足以帮助我。

到目前为止，我的想法是（不包括 if 语句）符号类似于 O(n^3) 但因为它们是嵌套的（以及其他人告诉我的东西），它有点让我失望。

请注意：这不是直接针对作业，但我们的任务是讨论我们为作业编写的代码及其复杂性。我们被告知要展示我们理解复杂性/正确性（一般来说，不是 BigO）以及它是如何应用的，但不要将它应用到我们的代码中，因为这样做太复杂了。我只是在考虑这样做，因为我想为将来更好地理解它。上面的代码也是一个随机示例，而不是我的实际代码，这意味着我仍然必须更改它以适应任何情况。

在此先感谢，我们在课堂上只看了大约 30 分钟的 BigO，经过大量阅读后，我觉得我自己太糊涂了。正如我所说，如果该代码不合适，我可以更改它。

4

1 回答 1

3

如果不清楚 N 是什么，那么您可以计算所有变量的性能，看看哪个变量的影响更大。在这种情况下，变量是 i、sr 和 t。严格来说，性能是 O(i * s * t)。r 不包括在内，因为它一直计数到 t，这是大 O 中的 t 的来源。

但问题是，由于 t 不能超过 2*s，用 t 代替 2s 会得到 O(i * s * 2s)。这与 O(2 * i * s^2) 相同。但是，在大 O 表示法中，所有系数都被视为等于 1。因此，它变为 O(i * s^2)。但是 i 和 s 不能超过 4，由于大 O 只关心最坏的情况，所以它变成 O(4 * 4^2)，因为大 O 只关心最坏的情况。这简化为 O(64)。但是，64 被认为是一个系数*。因此，实际的大 O 为 O(1)*。

*请注意，这并不完全正确，因为像 O(x + 64) 这样的情况变成了 O(x) 而不是 O(x + 1)，在这种情况下，64 实际上变成了零而不是一。

意思是，目前的算法是 O(1)，它本质上是独立于输入的。这就是为什么评论者会有些困惑。

这里的关键是，你可能有多个输入大小变量，它们独立地影响性能，你也可能有一个输出敏感算法，它的性能基于输入大小和输出大小。或者，您可能有一个不受输入大小影响的算法。

有关更详细的说明，请参阅Wikipedia 页面。

于 2013-01-27T05:34:33.570 回答