使用主定理求解递归T(n)= T(n/2)+ O(1)? [英] Solving the recurrence T(n) = T(n / 2) + O(1) using the Master Theorem?

问题描述

我正在尝试使用主定理及其递归概念来解决递归关系，以找出算法的复杂性，我如何证明这一点:

I'm trying to solve a recurrence relation to find out the complexity of an algorithm using the Master Theorem and its recurrences concepts, how can I prove that:

T(n) = T(n/2)+O(1)

是

T(n) = O(log(n)) ?

任何解释将不胜感激！

推荐答案

您的重复发生率是

T(n)= T(n/2)+ O(1)

T(n) = T(n / 2) + O(1)

由于主定理适用于以下形式的重复发生

Since the Master Theorem works with recurrences of the form

T(n)= aT(n/b)+ n ^c

在这种情况下，您有

• a = 1
• b = 2
• c = 0

由于c = log _b a(因为0 = log ₂ 1)，因此您位于

Since c = log_ba (since 0 = log₂ 1), you are in case two of the Master Theorem, which solves to Θ(n^c log n) = Θ(n⁰ log n) = Θ(log n).

希望这会有所帮助！

这篇关于使用主定理求解递归T(n)= T(n/2)+ O(1)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！