解决合并排序中的递归关系

我正在学习大O和重复。我遇到提到一个问题，解决合并排序中的递归关系

t = { 0, n =1 ; T(n-) , n > 1 }

谁能告诉我怎么去从这个为O（n^2）？

2012-02-25 hytriutucx

这是什么语言？ – 2012-02-25 13:14:40

我认为你的配方是有缺陷的。你是不是指t = {0，如果n == 1; T（n-1）如果n> 1}？（虽然它不是O（n²）） – 2012-02-25 13:30:52

现在的问题是无法解决的。对于初学者来说，T（）是什么？[注意，这不是递归方程，等式的左边是一个常数't'，而不是函数'T：N-> N']。 'n-'是什么意思？请检查您的课本并正确提出问题。 – amit 2012-02-25 13:56:56

在你的问题中functioin有复杂度为O（N），如果是O（N²）就应该是这样的：

T(x) = { 1, x =0 ; n + T(x-1) , x > 1 }

wheer n是t（x）的计算次数，则x/= 0

2012-02-25 17:24:22 nist

对于您提供的功能，'T（x）= n^x'。你可能意味着'T（n）= n + T（n-1）'，但它也可能是'T（n）= 4T（n/2）+1'，或者无限数量的可能性。 – amit 2012-02-25 17:37:08

仍然不对，请看editted comment。 – amit 2012-02-25 17:40:34

我不明白你想问什么。但是，通常，O（n^2）算法将具有在2级嵌套循环内执行的主要操作。像：

for(a=0;a<5;a++) { 
    for(b=0;b<5;b++) { 
     /* Some of the main operations of the algorithm */ 
    } 
    }

类似地，含有该算法的主要操作3级嵌套循环可能具有复杂度O（N^3）等。

（注：异常可能会出现上面的方法）

2012-02-25 13:15:35 check123

回答