如何获得欧米茄（N） [英] How to get Omega(n)

问题描述

予有下式的（N）= N *一个第（n-1）1;一个（0）= 0

I have the formula a(n) = n * a(n-1) +1 ; a(0) = 0

我怎样才能欧米茄，西塔或O符号从此无大师定理或没有任何人有一个很好的网站，了解说明

How can i get the Omega, Theta or O Notation from this without the Master Theorem or did anyone have a good site to understand the explanation

推荐答案

主定理甚至不适用，因此不能够使用它是没有太大的限制。

The Master theorem doesn't even apply, so not being able to use it isn't much of a restriction.

而在这里工作的一种方法是猜测的上限和下限，然后通过归纳证明这些猜测，如果猜测是不错的。

An approach which works here is to guess upper and lower bounds, and then prove these guesses by induction if the guesses are good.

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 10
a(4) = 41

有一个合理的猜测下界是，（N）> = N！对于n> 1。这是真实的对于n = 1。假设这是真的对于n = k-1个。

A reasonable guess for a lower bound is that a(n) >= n! for n>1. This is true for n=1. Suppose it is true for n=k-1.

a(k) = ka(k-1)+1 
     >= k (k-1)! + 1 
     >= k!. 

因此​​，如果这是真的对于n = k-1个，那么它是真对于n = k时，这样一（正）> = N！对所有正整数n和（N）=欧米茄（N！）。

So, if it is true for n=k-1, then it is true for n=k, so a(n) >= n! for all positive integers n, and a(n) = Omega(n!).

有一个合理的猜测上限是在（N）其中​​; = 2（N！）。这是真正的前几个值，但它原来是一个有点尴尬，证明采用感应。有时与归纳证明，这是更好地证明更强烈的东西。在这种情况下，最好是证明一个（正）所述; 2（N！），或者一个（n）的与所述;​​ = 2（N！） - 1。这是真实的对于n = 1。假设它是真正的N = K-1对某个k-1> = 1。然后

A reasonable guess for an upper bound is at a(n) <= 2(n!). This is true for the first few values, but it turns out to be a little awkward to prove using induction. Sometimes with inductive proofs, it is better to prove something stronger. In this case, it's better to prove that a(n) < 2(n!), or that a(n)<=2(n!)-1. This is true for n=1. Suppose it is true for n=k-1 for some k-1>=1. Then

a(k) = k(a(k-1))+1 
    <= k(2(k-1)!-1)+1 
     = 2(k!) +1-k 
    <= 2(k-1)!-1. 

因此​​，对于任意的n> = 1，一（正）所述; 2（N！）。因为我们有一个下限和上限的形式C *（N个！），A（N）=西塔（N！）。

So, for any n>=1, a(n) < 2(n!). Since we have a lower bound and an upper bound of the form c*(n!), a(n) = Theta(n!).

这篇关于如何获得欧米茄（N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！