求解Ω和Θ(O,Omega和Theta符号)

Question

我已经解决了一个递归关系,其运行时间为Θ(2 ^ n),指数时间.如何找到相同的递归关系的Ω和O.

我猜如果它是Θ(2 ^ n),它也应该是O(2 ^ n),我是对的吗？我如何找到Ω,下限？

我尝试解决递归关系:

T(n)= 2T(n-1)+ C.

Answer 1

如果函数是Θ(f(n)),则意味着它既是O(f(n))又是Ω(f(n))

反之亦然,如果函数既是O(f(n))又是Ω(f(n)),那么它是Θ(f(n))

证明这一点很简单:

g(n)=?(f(n)) => exists n0, c1 and c2 such that: c1f(n)<g(n)<c2f(n) for n>n0

只采取上半场:

exists n0 and c1 such that: c1f(n)<g(n) for n>n0 => g(n)=?(f(n))

下半场:

exists n0 and c2 such that: g(n)<c2f(n) for n>n0 => g(n)=O(f(n))

逆的证明是相似的.

编辑:关于Θ,O和Ω的含义有点亮.

你必须已经看过Θ,O和Ω的定义(如果没有,我刚刚在上面的证明中提到了它们中的所有三个).

除了他们的数学定义,他们的意思是什么？

基本上,想象他们是这样的:

• g(n) = O(f(n))这意味着当n变大时,f(n)总是具有更大的价值g(n).更确切地说,不是f(n)它本身,而是它的恒定倍数.例如,n+100是O(n^2)因为n>10,1*n^2>n+100.还有,对n>3,11*n^2>n+100.所有这些符号的含义是,常量不起重要作用,因为它f(n)决定了函数的增长方式.请注意,O表示法显示函数的上限,因此不是唯一的.例如,如果f(n)=O(n),那么它也是O(n^2)和O(nlogn)等,但(可能)不O(sqrt(n))

• g(n) = ?(f(n))这正是O的倒数.因此,它表明它f(n)是g(n)(再次乘以常数因子)的下限,并且它不是唯一的.例如,如果f(n)=?(n),然后也?(1)和?(1/n).你总是有

  g(n) = ?(f(n)) <=> f(n) = O(g(n))
  

• g(n) = ?((f(n))这是对函数增长的严格限制.它基本上意味着g(n)具有相同的增长f(n),尽管它可能不那么顺利f(n).这并不像f(n) Θ所做的那样美妙:你有一个算法,执行时间不是简单的表达,而是用Θ你可以分析它.g(n) = ?((f(n))是这样的图片:

  |                     ---- 2*f(n)
  |                    /    /\  ---(g(n)
  |                ----    /  \/    -------- f(n)
  |               /       /        /
  |           ----   /\  / --------
  |          /  -----  \/ /
  |      ----  /  --------
  |     /     /  /
  | ---- --------
  |/    /
  +---------------------------------------------
  

有趣的事实:

• f(n) = O(f(n))因为你有所有n,2*f(n)>f(n)(2是一个例子,任何大于1的常数都是好的).函数的最小上界是函数本身!
• 同样,f(n) = ?(f(n))和f(n) = ?(f(n)).此外,函数的最大下界是函数本身.
• Θ显示函数的确切增长,如果您为算法找到它,那么它就是最佳描述.然而,许多算法具有复杂的行为或者最好基于它们的输入具有不同的增长(例如,插入排序被?(n)给予排序的输入并且?(n^2)给出反向排序的输入)因此,找到算法的Θ并不总是可能的.
• O表示函数执行的上限.通常这是人们为他们的算法计算的.通过这样做,他们说,无论如何,我的算法并不比这更差,但在某些情况下它可能会更好.例如,插入排序是O(n^2).
• 有时O没有显示最佳(最小)上限,因为发现这太难了.在那些情况下,O仍然来救援.例如,如果你有一个算法在UI应用程序中使用大小为1000的输入(延迟,比如0.5s就可以了),那么如果你的算法是O(n^2)好的,即使算法的最坏情况执行是实际上低于那个(但你找到它太难了).最佳上限是算法最坏情况执行的增长率.在插入排序的示例中,最坏的情况是执行?(n^2),因此,您可以给算法的最佳上限是O(n^2)(与O(n^3)例如相反).
• Ω在实际中没有那么有用,你永远不想说我的算法是最好的这样,但可能会更糟糕(这是很糟糕的广告)!但是,在计算机科学中它非常有用.大多数时候,要证明某些事情不能以更好的方式完成.例如,如果有一个算法解决问题?(n^3),并且你证明无论解决问题的算法是什么?(n^3),那么这意味着永远不会有比你已经拥有的算法更好的算法(所以你有点告诉其他人不要找不到它,你找不到它)

有很多O-notation数学,不难理解或发明自己.一些例子是:

• O(f(n)+ g(n))= O(max(f(n),g(n)))
• O(f(n))+ O(g(n))= O(f(n)+ g(n))
• O(f(n))O(g(n))= O(f(n)g(n))
• O(cf(n))= O(f(n))其中c是常数

您可以通过将它们置于O表示法的定义中来立即证明其中的大部分内容.

第一条规则可能是最有用的.如果你的算法有两个部分,一个将一些大小的数组设置n为零,那么做一些O(nlogn)整体顺序就是这么O(n+nlogn)简单O(nlogn).

这意味着从数学上讲,最好有一千个O(nlogn)预处理和一个O(nlogn)解决问题的算法,而不是简洁的算法O(n^1.5).请注意,在实践中,它不一定更好.你为什么问？第一个是O(nlogn)第二个,O(n^1.5)所以第一个是你说的更好吗？请记住,O表示法渐近显示函数的行为.这意味着,是的,如果您的输出变得非常大,第一个算法(具有一千个预处理的算法)会更好,但在您的实际范围内n,1000nlogn可能会大得多n^1.5.