什么会导致一个算法有O（log n）的复杂性？ [英] What would cause an algorithm to have O(log n) complexity?

问题描述

我的大O的知识是有限的，当数方面显示方程中它更是抛出了我。

有人可以或许向我解释，简单来说有什么 O（log n）的算法？哪里的对数是从哪里来的？

此特地赶来了，当我试图解决这一期中考试的做法问题：

  

让X（1..N）和Y（1..N）的整数含有两个列表，每个分类后的非减顺序。举一个O（log n）的 - 时间算法找出中位数（或第n个最小整数）的所有2n个组合元素。为前中，X =（4，5，7，8，9）和Y =（3，5，8，9，10），则图7是合并的列表中（3，4，5，5，7的中值，8,8，9,9，10）。 [提示：二进制搜索的使用概念]

解决方案

我不得不承认，这是pretty的怪异你第一次看到一个O（log n）的算法，...其中在地球上的对数来从？然而，事实证明，有几种不同的方式，你可以得到一个日志术语出现在大O记法。这里有几个：

多次被恒定

分割

取任意数n;说，16，你有多少时间可以分为N的前两位你不是一个数量小于或等于一个？对于16，我们有

  16/2 = 8
 8/2 = 4
 4/2 = 2
 2/2 = 1
 

请注意，这最终采取四个步骤来完成。有趣的是，我们也有一个日志 ₂ 16 = 4。嗯...怎么样128？

 二分之一百二十八= 64
 64个/ 2 = 32
 32/2 = 16
 16/2 = 8
  8/2 = 4
  4/2 = 2
  2/2 = 1
 

这花了七个步骤，并记录 ₂ 128 = 7。这是一个巧合吗？没了！有一个很好的理由。假设我们把一个数n 2我倍。然后，我们得到的数n / 2 ^我。如果我们希望求解i的值，其中该值至多为1，我们得到

  

N / 2 ^我＆乐; 1

     

N'乐; 2 ^我

     

登录 ₂ N'乐;我

在换句话说，如果我们选择一个整数i即i＆格;登录 ₂ n，则跳水后的 n乘2 我时候，我们将有一个值，该值至多为1。最小的为我，这是保证大致登录<子> 2 N，因此，如果我们有一个算法，除以2，直到数得足够小，那么我们可以说，它终止于O（log n）的步骤。

这是很重要的细节是，它并不重要恒定你除以N的（只要它是大于一）;如果除以常数K，它会记录<子> K n步达到1因此，任何算法，通过一些分数多次将输入的大小需要O（log n）的迭代终止。这些迭代可能需要大量的时间，因此，净的运行时不必是O（log n）的，但步骤数将是对数的。

那么，这上来？一个典型的例子是的 二进制搜索 的，快速搜索算法排序的数组的值。该算法是这样的：

• 如果数组为空，则返回该元素不是present到数组中。
• 否则：
  • 看数组的中间元素。
  • 如果它等于我们要寻找的，返回成功的元素。
  • 如果是大于我们正在寻找的元素：
    • 扔掉阵列下半年。
    • 重复
  • 如果是小于我们正在寻找的元素：
    • 扔掉第一阵列的一半。
    • 重复

例如，阵列中搜索5

  1 3 5 7 9 11 13
 

我们会先看看中间元素：

  1 3 5 7 9 11 13
            ^
 

由于7> 5，并且由于数组排序，我们知道一个事实，即5号不能在后面的阵列的一半，所以我们只需将其丢弃。这使得

  1 3 5
 

所以，现在我们就来看看中间的元素在这里：

  1 3 5
    ^
 

由于第3版; 5，我们知道，5不能出现在第一个数组的一半，因此，我们可以抛出上半场阵列离开

  5
 

同样，我们看一下这个数组的中间：

  5
        ^
 

由于这正是我们要找的号码，我们可以报告说，5的确是到数组中。

那么，如何有效的呢？那么，在每次迭代我们扔剩下的数组元素的距离至少有一半。该算法一旦停止，因为数组为空，或者我们找到我们想要的值。在最坏的情况下，该元素是不存在的，所以我们保持数组的大小减半，直到我们用完元素。多久这个时间？那么，既然我们一直在削减一半的阵列一遍又一遍，我们将在最O（log n）的迭代完成，因为我们不能削减在阵列中一半为O（log n）的时间越跑前出数组中的元素。

算法下的 一般技术分而治之 （切割问题成件，解决这些碎片，然后把问题重新走到一起），往往为同样的原因对数项在其中 - 你不能保持去掉一些物体一半以上的O（log n）的时间。你可能想看看的 归并排序 的作为一个很好的例子。

处理值一位数字时间

有多少位是在基10号n？好了，如果有k个位数的号码，然后我们就会有一个最大的数字是10 ^K 的若干倍。最大K-位数是999 ... 9，k次，并且这等于10 ^{K + 1} - 1。因此，如果我们知道在于n为k位在它的话，我们知道n的值在10 ^{K + 1} - 1。如果我们要解决对于k的N而言，我们得到

  

N'乐; 10 ^{K + 1} - 1

     

N + 1文件; 10 ^{K + 1}

     

登录 ₁₀ （N + 1）与乐; K + 1

     

（日志 ₁₀ （N + 1）） - 1＆乐;氏/ P>

从中我们得到了k为约基10的对数为n的。换言之，在正的位数为O（log n）的

例如，让我们想想增加两个大数是太大，适合机器字的复杂性。假设我们有再psented以10 $ P $这些数字，我们会打电话给数m和n。添加它们的一种方法是通过等级学校的方法 - 把数字出一个数字的时间，然后从左侧向右工作。例如，增加1337和2065，我们会通过写号码的开出为

启动

  1 3 3 7
+ 2 0 6 5
==============
 

我们添加的最后一位数字，并携带1：

  1
    1 3 3 7
+ 2 0 6 5
==============
             2
 

然后我们加入第二个到最后（倒数第二）数字，携带1：

  1 1
    1 3 3 7
+ 2 0 6 5
==============
          0 2
 

接下来，我们添加了第三到最后（倒数第三）的数字：

  1 1
    1 3 3 7
+ 2 0 6 5
==============
       4 0 2
 

最后，我们添加了第四个到最后（preantepenultimate......我爱英语）位数：

  1 1
    1 3 3 7
+ 2 0 6 5
==============
    3 4 0 2
 

现在，有多少工作我们做了？我们共O（1）每位的工作做（即工作的，恒定量），并有O（最大{日志N，日志米}）共计需要被处理的数字。这给出了一个总的O（最大值{登录N，log M的}）的复杂性，因为我们需要访问每个数字在两个号码。

许多算法得到的O从工作一个数字在一些基本时间（log n）的任期在其中。一个典型的例子是的 基数排序 的，这种种整数一位数字的时间。有基数排序许多种，但它们通常时间为O运行（N日志U），其中U是最大可能整数正在被排序。这样做的原因是，那种每遍需要O（n）的时间，共有O（日志U）来处理每一个的O（日志U）数量最多的数字进行排序所需的迭代。许多先进的算法，如 Gabow的最短路径算法或的缩放版本< A HREF =htt​​p://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm>福特 - 富尔克森最大流算法，有其复杂性日志来看，因为他们的工作一个数字的时间。

---

至于你关于你如何解决这个问题的第二个问题，你可能想看看这相关的问题其中探讨了更先进的应用。鉴于此处所描述的问题的一般结构，你现在可以有一个更好地了解如何思考问题，当你知道有在结果的日志项，因此我建议不要看答案，直到你给它一些思考。

希望这有助于！

My knowledge of big-O is limited, and when log terms show up in the equation it throws me off even more.

Can someone maybe explain to me in simple terms what a O(log n) algorithm is? Where does the logarithm come from?

This specifically came up when I was trying to solve this midterm practice question:

Let X(1..n) and Y(1..n) contain two lists of integers, each sorted in nondecreasing order. Give an O(log n)-time algorithm to find the median (or the nth smallest integer) of all 2n combined elements. For ex, X = (4, 5, 7, 8, 9) and Y = (3, 5, 8, 9, 10), then 7 is the median of the combined list (3, 4, 5, 5, 7, 8, 8, 9, 9, 10). [Hint: use concepts of binary search]

解决方案

I have to agree that it's pretty weird the first time you see an O(log n) algorithm... where on earth does that logarithm come from? However, it turns out that there's several different ways that you can get a log term to show up in big-O notation. Here are a few:

Repeatedly dividing by a constant

Take any number n; say, 16. How many times can you divide n by two before you get a number less than or equal to one? For 16, we have that

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

Notice that this ends up taking four steps to complete. Interestingly, we also have that log₂ 16 = 4. Hmmm... what about 128?

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

This took seven steps, and log₂ 128 = 7. Is this a coincidence? Nope! There's a good reason for this. Suppose that we divide a number n by 2 i times. Then we get the number n / 2ⁱ. If we want to solve for the value of i where this value is at most 1, we get

n / 2ⁱ ≤ 1

n ≤ 2ⁱ

log₂ n ≤ i

In other words, if we pick an integer i such that i ≥ log₂ n, then after diving n by 2 i times we'll have a value that is at most 1. The smallest i for which this is guaranteed is roughly log₂ n, so if we have an algorithm that divides by 2 until the number gets sufficiently small, then we can say that it terminates in O(log n) steps.

An important detail is that it doesn't matter what constant you're dividing n by (as long as it's greater than one); if you divide by the constant k, it will take log_k n steps to reach 1. Thus any algorithm that repeatedly divides the input size by some fraction will need O(log n) iterations to terminate. Those iterations might take a lot of time and so the net runtime needn't be O(log n), but the number of steps will be logarithmic.

So where does this come up? One classic example is binary search, a fast algorithm for searching a sorted array for a value. The algorithm works like this:

• If the array is empty, return that the element isn't present in the array.
• Otherwise:
  • Look at the middle element of the array.
  • If it's equal to the element we're looking for, return success.
  • If it's greater than the element we're looking for:
    • Throw away the second half of the array.
    • Repeat
  • If it's less than the the element we're looking for:
    • Throw away the first half of the array.
    • Repeat

For example, to search for 5 in the array

1   3   5   7   9   11   13

We'd first look at the middle element:

1   3   5   7   9   11   13
            ^

Since 7 > 5, and since the array is sorted, we know for a fact that the number 5 can't be in the back half of the array, so we can just discard it. This leaves

1   3   5

So now we look at the middle element here:

1   3   5
    ^

Since 3 < 5, we know that 5 can't appear in the first half of the array, so we can throw the first half array to leave

        5

Again we look at the middle of this array:

        5
        ^

Since this is exactly the number we're looking for, we can report that 5 is indeed in the array.

So how efficient is this? Well, on each iteration we're throwing away at least half of the remaining array elements. The algorithm stops as soon as the array is empty or we find the value we want. In the worst case, the element isn't there, so we keep halving the size of the array until we run out of elements. How long does this take? Well, since we keep cutting the array in half over and over again, we will be done in at most O(log n) iterations, since we can't cut the array in half more than O(log n) times before we run out of array elements.

Algorithms following the general technique of divide-and-conquer (cutting the problem into pieces, solving those pieces, then putting the problem back together) tend to have logarithmic terms in them for this same reason - you can't keep cutting some object in half more than O(log n) times. You might want to look at merge sort as a great example of this.

Processing values one digit at a time

How many digits are in the base-10 number n? Well, if there are k digits in the number, then we'd have that the biggest digit is some multiple of 10^k. The largest k-digit number is 999...9, k times, and this is equal to 10^{k + 1} - 1. Consequently, if we know that n has k digits in it, then we know that the value of n is at most 10^{k + 1} - 1. If we want to solve for k in terms of n, we get

n ≤ 10^k+1 - 1

n + 1 ≤ 10^k+1

log₁₀ (n + 1) ≤ k + 1

(log₁₀ (n + 1)) - 1 ≤ k

From which we get that k is approximately the base-10 logarithm of n. In other words, the number of digits in n is O(log n).

For example, let's think about the complexity of adding two large numbers that are too big to fit into a machine word. Suppose that we have those numbers represented in base 10, and we'll call the numbers m and n. One way to add them is through the grade-school method - write the numbers out one digit at a time, then work from the right to the left. For example, to add 1337 and 2065, we'd start by writing the numbers out as

    1  3  3  7
+   2  0  6  5
==============

We add the last digit and carry the 1:

          1
    1  3  3  7
+   2  0  6  5
==============
             2

Then we add the second-to-last ("penultimate") digit and carry the 1:

       1  1
    1  3  3  7
+   2  0  6  5
==============
          0  2

Next, we add the third-to-last ("antepenultimate") digit:

       1  1
    1  3  3  7
+   2  0  6  5
==============
       4  0  2

Finally, we add the fourth-to-last ("preantepenultimate"... I love English) digit:

       1  1
    1  3  3  7
+   2  0  6  5
==============
    3  4  0  2

Now, how much work did we do? We do a total of O(1) work per digit (that is, a constant amount of work), and there are O(max{log n, log m}) total digits that need to be processed. This gives a total of O(max{log n, log m}) complexity, because we need to visit each digit in the two numbers.

Many algorithms get an O(log n) term in them from working one digit at a time in some base. A classic example is radix sort, which sorts integers one digit at a time. There are many flavors of radix sort, but they usually run in time O(n log U), where U is the largest possible integer that's being sorted. The reason for this is that each pass of the sort takes O(n) time, and there are a total of O(log U) iterations required to process each of the O(log U) digits of the largest number being sorted. Many advanced algorithms, such as Gabow's shortest-paths algorithm or the scaling version of the Ford-Fulkerson max-flow algorithm, have a log term in their complexity because they work one digit at a time.

---

As to your second question about how you solve that problem, you may want to look at this related question which explores a more advanced application. Given the general structure of problems that are described here, you now can have a better sense of how to think about problems when you know there's a log term in the result, so I would advise against looking at the answer until you've given it some thought.

Hope this helps!

这篇关于什么会导致一个算法有O（log n）的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！