决定算法的大O符号

问题描述：

我对我的任务有疑问。我需要决定什么是大O表征这个下面的算法：决定算法的大O符号

enter image description here

我猜对问题1回答是O（n）和问题2是O（log n）的，但我有点困惑如何说明原因。我的答案是否正确？你能解释为什么这种特征是这样的吗？

我很确定你必须确定这一点。无论您的决定如何，该算法的Big-O性能**都是**。 – 2014-08-30 15:10:18

你的猜测是非常正确的，Q1很简单，因为Q2-尝试搜索二进制搜索的复杂性！ – 2014-08-30 15:10:27

Stackoverflow不是要求别人做作业的地方！如果你有一个特定的问题，你已经努力解决，但不能解决，如果你可以说你的问题是一个问题，我们会提供帮助。 – ericbn 2014-08-30 15:14:08

答

问题1：O(n)，因为它按常量（1）递增。
第一循环O(n)秒循环也O(n)
总O(n) + O(n) = O(n)

问题2：O(lg n)它的二进制搜索。

这是O(lg n)，因为问题每次都减半。

如果阵列大小为n第一秒是n/2则n/4 ..... 1。

n/2^i = 1 =>n = 2^i =>i = log(n)。

答

是的，你的回答是对的。第一个很简单。 2 单独for循环。如此有效地它的O(n)。

第二个实际上很棘手。实际上，您将输入大小除以2（一半），这实际上会导致时间复杂度为O(log n)。