复杂性计算和逻辑概念

Question

我正在尝试找出下面代码的复杂性，不知道我的逻辑是否正确，如有错误请指正

1)

For a = 1 to N
    j = v
    j = j / 2    
    k = i
    While k >= 1
        do some kind of processing
        k = k / 2     // integer division

2)

For i = 1 to N

        d = d / 2    // integer division
    k = i
    While k >= 1

        k = k-1

这个也应该是N * log N?

3)

For i = 1 to N                  functiontwo(x)
    call functiontwo(i)           if (x <= 0)
                                    return some value

这个应该也是n * log N，还是我错了，因为调用的是函数二，而函数二是log n？

请让我知道我的方法是否正确，或者给出更好地找出循环逻辑的建议，谢谢。

Answer 1

（免责声明：我已经有一段时间没有做这些了，但由于还没有其他人加入，我的两分钱总比没有好。）

我相信您在 #1 上的逻辑是正确的。第i个循环应该是O(N)，第j和k个循环看起来是O(logN)，使得整体O(NlogN).

不过，我质疑你对 #2 的结论。由于 k 递减 1 而不是除以，因此在我看来 k 循环将是 O(N)，总体上 O(N^2)。

嗯...#3 很奇怪。我明白为什么您的第一个想法是 O(NlogN)。该部门通常会使它类似于#1。除了...发送到 functiontwo 的第一个参数将是 i 循环中的正值。由于 x > 0，它随后将使用原始参数的一半调用 functiontwo，这仍然是正数。这会一次又一次地发生，等等。我内心的数学家开始认为这永远不会结束。但我想有人可能会争辩说，最终您将达到数字数据类型的精度极限，并最终使 x/2 的结果非常接近于零，以至于计算机将其计为零。在那种情况下，我想 O(NlogN) 是准确的。

顺便说一句，我对 #3 的回答是假设 x/2 不是整数除法，因为你为其他人指定了它，但不是这个。

复杂性计算和逻辑概念

complexity calculation and logic concept

function

time-complexity