大O的运行时间功能

Question

找到大O运行时间为每个功能：

1. T(n) = T(n - 2) + n²
   我们的答案：n²，n³
2. T(n) = 3T(n/2) + n
   我们的答案：O(n log n)，O(nlog₂3)
3. T(n) = 2T(n/3) + n
   我们的答案：O(n log base 3 of n),O(n)
4. T(n) = 2T(n/2) + n^3
   我们的答案：O(n³ log₂n)，O(n³)

因此，我们无法决定对每个问题的正确答案。

我们都得到了不同的结果，并且希望在什么运行时间将是外界舆论。

在此先感谢。

Answer 1

澄清的位：
在问题的功能似乎是运行时间功能通过T()名字和他们n参数作为暗示。一个更微妙的提示是，它们都是递归的，递归函数是一个常见事件，当我们生成一个函数来描述一个算法的运行时间时（即使算法本身没有正式使用递归）。事实上，递推公式是很不方便的形式，这就是为什么我们使用大O符号，以更好地总结了算法的行为。

运行时间函数是参数（或多个）参数化一个数学表达式，其允许计算用于一个算法的运行时间[有时近似]相对值，给定的特定值（S）。比如这里的情况下，运行时间函数通常只有一个参数，通常命名n，对应的项目算法，预计总人数与搜索算法上下工夫/带（对于例如，它可能是总数据库中的记录数，使用排序算法可以是未排序列表中的条目数和路径查找算法的数量，图中节点的数量....）。在一些情况下，运行时间函数可以具有多个参数，例如，在图形上执行某些变换的算法的性能可结合到两个节点的总数和顶点的总数量或连接的平均数目两个节点之间，等等

在手（对于这似乎是家庭作业，因此我的部分答案），因此，找到一种Big O表达有资格每个运行时间函数的上边界限制的任务，，无论它们可能对应的底层算法是什么。任务是不，寻找和排位赛的算法产生的函数的结果（这第二个可能性也是锻炼算法班CS的cursus的一个很常见的类型，但显然不是什么这里需要。）

因此，问题是计算机科学本身的数学问题之一。
基本上，当n接近无穷大时，需要找到每个函数的极限（或其近似值）。
这note from Prof. Jeff Erikson在伊利诺伊大学厄巴纳香槟分校提供一个很好的介绍，以解决复发。
虽然解决复发有一些捷径，特别是如果一个人有一个良好的微积分命令，一个通用的方法是猜测答案，然后通过归纳证明。诸如Excel之类的工具，诸如Python之类的编程语言中的一些片段，或MATLAB或Sage可用于产生前几百个值（或超出）的表以及诸如n^2，n^3，n之类的值！以及功能条款的比例;这些表通常提供足够的洞察函数来查找函数的封闭形式。
功能a）
    O(n^2)是肯定错了：

关于答案的几个提示的问题上市
       前几个值的序列中的快速检查显示n^2比T（n）更加小得多
    O(n^3)另一方面似乎系统地大于随着n向大数字增长，。仔细看，O(n^3)实际上是该函数的大O符号的命令，但是O(n^3/6)是系统地超过T（n）的值的更精确的符号[对于更大的n值和/或作为n倾向于无穷大]，但仅与更粗略的n^3估计值相比分数部分。
一个可以确认O(n^3/6)是，通过感应：

T(n) = T(n-2) + n^2 // (1) by definition 
T(n) = n^3/6  // (2) our "guess" 
T(n) = ((n - 2)^3/6) + n^2 // by substitution of T(n-2) by the (2) expression 
    = (n^3 - 2n^2 -4n^2 -8n + 4n - 8)/6 + 6n^2/6 
    = (n^3 - 4n -8)/6 
    = n^3/6 - 2n/3 - 4/3 
    ~= n^3/6  // as n grows towards infinity, the 2n/3 and 4/3 factors 
        // become relatively insignificant, leaving us with the 
        // (n^3/6) limit expression, QED