0

我在这个函数中有 3 个问题，

Sum = 0 
MyFunction (N)
        M = 1,000,000 
        If (N > 1)
                For I = 1 to M do
                        Sum = 0
                        J = 1 
                        Do 
                                Sum = Sum + J
                                J = J + 2
                        While J < N 
                End For
                If (MyFunction(N / 2) % 3 == 0)
                        Return (2 * MyFunction(N / 2))
                Else
                        Return (4 * MyFunction(N / 2))
                End If
        Else
                Return 1        
        End If
End MyFunction

第一个问题是：代码的非递归部分的复杂性是什么？

我认为非递归部分是那个循环

For I = 1 to M do
                        Sum = 0
                        J = 1 
                        Do 
                                Sum = Sum + J
                                J = J + 2
                        While J < N 
                End For

我的回答是M * log(n)，但我的幻灯片说不是M * log (n)！我需要对此作出解释。

第二个问题是： MyFunction 前面代码的正确复现是什么？

当我看到这些代码行时

If (MyFunction(N / 2) % 3 == 0)
                        Return (2 * MyFunction(N / 2))
                Else
                        Return (4 * MyFunction(N / 2))
                End If

我认为它是T(n) = T(n/2) + Theta(non-recursive)，因为 if 将执行 2 个调用之一。

这个答案又是错误的。

第三个是： MyFunction 的复杂度是多少？

我基于 2 个问题的回答是T(n) = T(n/2) + M * lg n ，总运行时间是M * lg n。

4

1 回答 1

2

让我们一次看这件作品。

首先，这是代码的非递归部分：

For I = 1 to M do
     Sum = 0
     J = 1 
     Do 
         Sum = Sum + J
         J = J + 2
     While J < N 
End For

外循环将运行 Θ(M) 次。由于 M 是一个固定常数（一百万），循环将运行 Θ(1) 次。

在循环内部，内部 while 循环将运行 Θ(N) 次，因为在每次迭代中 J 增加 2 并在 J 达到或超过 N 时立即停止。因此，这个循环嵌套完成的总工作是 Θ(N) : Θ(N) 工作 Θ(1) 次。

现在，让我们看一下这部分：

If (MyFunction(N / 2) % 3 == 0)
    Return (2 * MyFunction(N / 2))
Else
    Return (4 * MyFunction(N / 2))
End If

该if语句将对 size 的输入进行一次递归调用N / 2，然后根据结果，总会有第二次 size 的递归调用N / 2（因为您没有缓存结果）。

这给出了运行时的以下递归关系：

T(n) = 2T(n / 2) + Θ(n)

使用主定理，这解决了 Θ(n log n)。

希望这可以帮助！

于 2013-10-24T19:09:16.397 回答