決定算法的大O符號

Question

我對我的任務有疑問。 我需要決定什麼是大O表徵這個下面的算法：

我猜對問題1回答是O（n）和問題2是O（log n）的，但我有點困惑 如何說明原因。我的答案是否正確？你能解釋爲什麼這種特徵是這樣的嗎？

Answer 1

問題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)。

Answer 2

是的，你的回答是對的。第一個很簡單。 2 單獨for循環。如此有效地它的O(n)。

第二個實際上很棘手。實際上，您將輸入大小除以2（一半），這實際上會導致時間複雜度爲O(log n)。