算法：主定理

Question

3

主定理可用于解决递归关系，如 T(n)= aT(n/b)+f(n)。

因此，如果f(n)=O(n)或f(n)=cn，这两个值相同吗？我可以将主定理用于f(n)=cn吗？

- pratik watwani

当考虑渐近关系时，常数（如 c）通常被忽略。这是因为随着 n 变得足够大，常数使得计算内存消耗和运行时间变得非常困难。这意味着 f(n)=n，等同于 f(n)=O(n)。 - Evan Bechtol

2个回答

2

如果我理解问题正确，f(n)=cn（其中c是常数）属于O(n)；可以应用主定理。

- Codor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mort · Accepted Answer

假设 c 是一个常数，并且如果我正确理解了你的问题，那么对于f(n) = O(n)和f(n) = cn，它们的解决方案将是相同的，因为cn = O(n)，因此可以应用主定理来解决此递归问题。