上界VS下界的一个算法的最坏情况下的运行时间

本文介绍了上界VS下界的一个算法的最坏情况下的运行时间的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我学习算法分析。我明白了的最坏情况下的运行时间的算法的概念。

I am learning about analysis of algorithms. I understand the concept of the worst case running time of an algorithm.

然而，在运行的算法的时间上的最坏情况下的上限和下限？

However, what are upper and lower bounds on the worst case running time of an algorithm?

什么可以是一个例子，其中一个的上限的用于运行算法的时间的最坏的情况是，从不同的的下限的运行的同时最坏的情况下算法？

What can be an example where an upper bound for the worst case running time of an algorithm is different from the lower bound for the worst case running time of the same algorithm?

推荐答案

一个函数 F（N）， G（N）是上限（大O ），如果对于足够大N， F（N）其​​中​​= C * G（N），对于恒定 C 。 [G主宰F] G（n）是下限（大欧米茄）如果足够大N， F（N）＆GT; = C * G（N），对于恒定 C 。 [F主导G]

for a function f(n), g(n) is an upper bound (big O) if for "big enough n", f(n)<=c*g(n), for a constant c. [g dominates f] g(n) is lower bound (big Omega) if for "big enough n", f(n) >= c*g(n), for a constant c. [f dominates g]

如果 G（N）既上限和下限的 F（N） [用不同的C的]，我们说G（N）是一个严密开往F（N）[大θ1

If g(n) is both upper bound and lower bound of f(n) [with different c's], we say g(n) is a tight bound for f(n) [Big theta]

使用范例上限，而不是紧一：有的时候是很难找到紧约束，例如对的斐波纳契递归算法。因此，我们找到一个简单的上界O（2 ^ n）的，很容易。更多信息以本答案中的post

Use example for upper bound instead of tight one: some times it is hard to find tight bound, such as for the fibonacci recursive algorithm. so we find an easy upper bound of O(2^n), easily. more info is found in answers in this post