下面这段代码的渐近运行时间是多少？

问题描述：

if (N % 2 == 0) // N is even 
for (int i = 0; i < N; i = i+1) 
    for (int j = 0; j < N; j = j+1) 
     A[i] = j; 
else // N is odd 
for (int i = 0; i < N; i = i+1) 
    A[i] = i;

如果N是偶数，我们看到的运行时间为O（n^2），N为奇数时的运行时间为O（n）。但我无法确定渐近的运行时间。

可能的答案是：

〜O（N）
〜为O（n^2）
〜O（N * SQRT（N））
〜为O（n日志n）

**提示：**大O是一个上限。 – interjay

对于什么是值得的，如果问题没有指定一个严格的界限，你总是可以选择最大的答案，它在技术上对于大O来说是正确的。 – kevmo314

答

没有一个简单的函数可以用来渐近地严格限制运行时。如您所述，运行时在每一步都会在线性和二次方之间振荡。你可以说运行时间是O（n ）和Ω（n），但是没有定义分段函数，你不能在这里给出一个Θ的界限。

Bump ............ – TheFermat

对不起，你想要碰撞什么？ – templatetypedef

Theta（n^{3/2 +（（ - 1）^ n）/ 2}） –

下面这段代码的渐近运行时间是多少？

相关推荐