알고리즘이 O (log n) 복잡성을 갖게하는 원인은 무엇입니까?

알고리즘이 O (log n) 복잡성을 갖게하는 원인은 무엇입니까?

---

big-O에 대한 나의 지식은 제한적이며 로그 용어가 방정식에 나타날 때 나를 더 많이 버립니다.

누군가가 O(log n)알고리즘이 무엇인지 간단한 용어로 설명 할 수 있습니까 ? 로그는 어디에서 왔습니까?

이것은 제가 중간 고사 문제를 풀려고 할 때 특별히 나왔습니다.

X (1..n) 및 Y (1..n)에 각각 감소하지 않는 순서로 정렬 된 두 개의 정수 목록이 포함되도록합니다. 결합 된 모든 2n 요소의 중앙값 (또는 n 번째로 작은 정수)을 찾기 위해 O (log n)-시간 알고리즘을 제공합니다. 예를 들어 X = (4, 5, 7, 8, 9) 및 Y = (3, 5, 8, 9, 10)의 경우 7은 결합 된 목록의 중앙값입니다 (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10). [힌트 : 이진 검색 개념 사용]

---

나는 당신이 O (log n) 알고리즘을 처음 볼 때 꽤 이상하다는 것에 동의해야합니다 ... 도대체 그 로그는 어디에서 왔습니까? 그러나 로그 용어를 big-O 표기법으로 표시하는 방법에는 여러 가지가 있습니다. 다음은 몇 가지입니다.

상수로 반복적으로 나누기

임의의 수 n; 16. 1보다 작거나 같은 숫자를 얻기 전에 n을 2로 몇 번 나눌 수 있습니까? 16 명의 경우

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

완료하는 데 4 단계가 필요합니다. 흥미롭게도 log ₂ 16 = 4 도 있습니다 . 음 ... 128은 어떻습니까?

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

이 일곱 개 조치를 취했다 및 로그 ₂ 128 = 7이 우연의 일치인가를? 아니! 이것에 대한 좋은 이유가 있습니다. 숫자 n을 2 i로 나눈다 고 가정합니다. 그런 다음 n / 2 ^i를 얻습니다 . 이 값이 최대 1 인 i의 값을 구하려면

n / 2 ^나는 ≤ 1

n ≤ 2 ^나는

로그 ₂ N ≤를 난

즉, i ≥ log ₂ n 인 정수 i를 선택하면 n을 i로 반으로 나눈 값은 최대 1이됩니다. 이것이 보장되는 가장 작은 i는 대략 log _2입니다. n이므로 숫자가 충분히 작아 질 때까지 2로 나누는 알고리즘이 있으면 O (log n) 단계에서 종료된다고 말할 수 있습니다.

중요한 세부 사항은 n을 (1보다 큰 한) 어떤 상수로 나눌 것인지는 중요하지 않다는 것입니다. 상수 k로 나누면 1에 도달하는 데 log _k n 단계가 필요합니다. 따라서 입력 크기를 일부 분수로 반복적으로 나누는 알고리즘은 종료하려면 O (log n) 반복이 필요합니다. 이러한 반복은 많은 시간이 걸릴 수 있으므로 순 런타임은 O (log n) 일 필요는 없지만 단계 수는 대수입니다.

그래서 이것은 어디에서 나옵니까? 한 가지 고전적인 예는 정렬 된 배열에서 값을 검색하는 빠른 알고리즘 인 이진 검색 입니다. 알고리즘은 다음과 같이 작동합니다.

• 배열이 비어 있으면 해당 요소가 배열에 없음을 반환합니다.
• 그렇지 않으면:
  • 배열의 중간 요소를보십시오.
  • 우리가 찾고있는 요소와 같으면 성공을 반환합니다.
  • 우리가 찾고있는 요소보다 큰 경우 :
    • 배열의 두 번째 절반을 버립니다.
    • 반복
  • 우리가 찾고있는 요소보다 작은 경우 :
    • 배열의 전반부를 버립니다.
    • 반복

예를 들어 배열에서 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 ≤ k

여기서 k는 n의 밑이 10 인 로그라는 것을 알 수 있습니다. 즉, n의 자릿수는 O (log n)입니다.

예를 들어 너무 커서 기계어에 맞지 않는 두 개의 큰 숫자를 더하는 복잡성에 대해 생각해 봅시다. 10 진수로 표시된 숫자가 있고 숫자 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

다음으로 마지막에서 세 번째 ( "antepenultimate") 숫자를 추가합니다.

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

마지막으로 마지막에서 네 번째 숫자 ( "preantepenultimate"... I love English)를 추가합니다.

       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!

---

When we talk about big-Oh descriptions, we are usually talking about the time it takes to solve problems of a given size. And usually, for simple problems, that size is just characterized by the number of input elements, and that's usually called n, or N. (Obviously that's not always true-- problems with graphs are often characterized in numbers of vertices, V, and number of edges, E; but for now, we'll talk about lists of objects, with N objects in the lists.)

We say that a problem "is big-Oh of (some function of N)" if and only if:

For all N > some arbitrary N_0, there is some constant c, such that the runtime of the algorithm is less than that constant c times (some function of N.)

In other words, don't think about small problems where the "constant overhead" of setting up the problem matters, think about big problems. And when thinking about big problems, big-Oh of (some function of N) means that the run-time is still always less than some constant times that function. Always.

In short, that function is an upper bound, up to a constant factor.

So, "big-Oh of log(n)" means the same thing that I said above, except "some function of N" is replaced with "log(n)."

So, your problem tells you to think about binary search, so let's think about that. Let's assume you have, say, a list of N elements that are sorted in increasing order. You want to find out if some given number exists in that list. One way to do that which is not a binary search is to just scan each element of the list and see if it's your target number. You might get lucky and find it on the first try. But in the worst case, you'll check N different times. This is not binary search, and it is not big-Oh of log(N) because there's no way to force it into the criteria we sketched out above.

You can pick that arbitrary constant to be c=10, and if your list has N=32 elements, you're fine: 10*log(32) = 50, which is greater than the runtime of 32. But if N=64, 10*log(64) = 60, which is less than the runtime of 64. You can pick c=100, or 1000, or a gazillion, and you'll still be able to find some N that violates that requirement. In other words, there is no N_0.

If we do a binary search, though, we pick the middle element, and make a comparison. Then we throw out half the numbers, and do it again, and again, and so on. If your N=32, you can only do that about 5 times, which is log(32). If your N=64, you can only do this about 6 times, etc. Now you can pick that arbitrary constant c, in such a way that the requirement is always met for large values of N.

With all that background, what O(log(N)) usually means is that you have some way to do a simple thing, which cuts your problem size in half. Just like the binary search is doing above. Once you cut the problem in half, you can cut it in half again, and again, and again. But, critically, what you can't do is some preprocessing step that would take longer than that O(log(N)) time. So for instance, you can't shuffle your two lists into one big list, unless you can find a way to do that in O(log(N)) time, too.

(NOTE: Nearly always, Log(N) means log-base-two, which is what I assume above.)

---

In the following solution, all the lines with a recursive call are done on half of the given sizes of the sub-arrays of X and Y. Other lines are done in a constant time. The recursive function is T(2n)=T(2n/2)+c=T(n)+c=O(lg(2n))=O(lgn).

You start with MEDIAN(X, 1, n, Y, 1, n).

MEDIAN(X, p, r, Y, i, k) 
if X[r]<Y[i]
    return X[r]
if Y[k]<X[p]
    return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
    if X[q+1]>Y[j] and Y[j+1]>X[q]
        if X[q]>Y[j]
            return X[q]
        else
            return Y[j]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q+1, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j+1, k)
else
    if X[q]>Y[j] and Y[j+1]>X[q-1]
        return Y[j]
    if Y[j]>X[q] and X[q+1]>Y[j-1]
        return X[q]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j, k)

---

The Log term pops up very often in algorithm complexity analysis. Here are some explanations:

1. How do you represent a number?

Lets take the number X = 245436. This notation of “245436” has implicit information in it. Making that information explicit:

X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0

Which is the decimal expansion of the number. So, the minimum amount of information we need to represent this number is 6 digits. This is no coincidence, as any number less than 10^d can be represented in d digits.

So how many digits are required to represent X? Thats equal to the largest exponent of 10 in X plus 1.

==> 10 ^ d > X
==> log (10 ^ d) > log(X)
==> d* log(10) > log(X)
==> d > log(X) // And log appears again...
==> d = floor(log(x)) + 1

Also note that this is the most concise way to denote the number in this range. Any reduction will lead to information loss, as a missing digit can be mapped to 10 other numbers. For example: 12* can be mapped to 120, 121, 122, …, 129.

2. How do you search for a number in (0, N - 1)?

Taking N = 10^d, we use our most important observation:

The minimum amount of information to uniquely identify a value in a range between 0 to N - 1 = log(N) digits.

This implies that, when asked to search for a number on the integer line, ranging from 0 to N - 1, we need at least log(N) tries to find it. Why? Any search algorithm will need to choose one digit after another in its search for the number.

The minimum number of digits it needs to choose is log(N). Hence the minimum number of operations taken to search for a number in a space of size N is log(N).

Can you guess the order complexities of binary search, ternary search or deca search?
Its O(log(N))!

3. How do you sort a set of numbers?

When asked to sort a set of numbers A into an array B, here’s what it looks like ->

Permute Elements

Every element in the original array has to be mapped to it’s corresponding index in the sorted array. So, for the first element, we have n positions. To correctly find the corresponding index in this range from 0 to n - 1, we need…log(n) operations.

The next element needs log(n-1) operations, the next log(n-2) and so on. The total comes to be:

==> log(n) + log(n - 1) + log(n - 2) + … + log(1)

Using log(a) + log(b) = log(a * b),

==> log(n!)

This can be approximated to nlog(n) - n.
Which is O(n*log(n))!

Hence we conclude that there can be no sorting algorithm that can do better than O(n*log(n)). And some algorithms having this complexity are the popular Merge Sort and Heap Sort!

These are some of the reasons why we see log(n) pop up so often in the complexity analysis of algorithms. The same can be extended to binary numbers. I made a video on that here.
Why does log(n) appear so often during algorithm complexity analysis?

Cheers!

---

We call the time complexity O(log n), when the solution is based on iterations over n, where the work done in each iteration is a fraction of the previous iteration, as the algorithm works towards the solution.

---

Can't comment yet... necro it is! Avi Cohen's answer is incorrect, try:

X = 1 3 4 5 8
Y = 2 5 6 7 9

None of the conditions are true, so MEDIAN(X, p, q, Y, j, k) will cut both the fives. These are nondecreasing sequences, not all values are distinct.

Also try this even-length example with distinct values:

X = 1 3 4 7
Y = 2 5 6 8

Now MEDIAN(X, p, q, Y, j+1, k) will cut the four.

Instead I offer this algorithm, call it with MEDIAN(1,n,1,n):

MEDIAN(startx, endx, starty, endy){
  if (startx == endx)
    return min(X[startx], y[starty])
  odd = (startx + endx) % 2     //0 if even, 1 if odd
  m = (startx+endx - odd)/2
  n = (starty+endy - odd)/2
  x = X[m]
  y = Y[n]
  if x == y
    //then there are n-2{+1} total elements smaller than or equal to both x and y
    //so this value is the nth smallest
    //we have found the median.
    return x
  if (x < y)
    //if we remove some numbers smaller then the median,
    //and remove the same amount of numbers bigger than the median,
    //the median will not change
    //we know the elements before x are smaller than the median,
    //and the elements after y are bigger than the median,
    //so we discard these and continue the search:
    return MEDIAN(m, endx, starty, n + 1 - odd)
  else  (x > y)
    return MEDIAN(startx, m + 1 - odd, n, endy)
}

참고URL : https://stackoverflow.com/questions/9152890/what-would-cause-an-algorithm-to-have-olog-n-complexity