[Data Structure & Algorithm] Time Complexity - O(logn)

Q) I cannot understand how to identify a function with a logN time.

- binary search는 주어진 배열을 반으로 나눠 검색하고, 거기서 또 반으로 나누고 검색해서 보통 배열 전체를 하나하나 검색하는 것보다 O(n) 더 조금 걸린다. 이건 뭔가 외우듯이? 알게되고 Time Complexity를 공부하고, 문제를 풀때 뭔가 linear time(O(n)) 이나 o(n^2) 같이 딱 개념이 안 잡혔다. Binary Search Tree 튜토리얼에서 배우고 리뷰하는겸 정리하면서 구글링 하다가 Stack Overflow에서  O(logn)에 대한 설명이 잘 되어있는 것을 찾았다. 

 

 

The most common attributes of the logarithmic running-time function are that:

: 가장 흔한 logN 실행 시간의 함수의 속성

• the choice of the next element on which to perform some action is one of several possibilities, and
• only one will need to be chosen. 
• -> 어떤 작업을 수행할 다음 요소의 선택은 여러 가지 가능성 중 하나이며, 하나만 선택하면 된다. 

or

• the elements on which the action is performed are digits of n
• -> 또는, 작업이 수행되는 요소들은 n개의 자리수이다. 

 

This is why, for example, looking up people in a phone book is O(log n). You don't need to check every person in the phone book to find the right one; instead, you can simply divide-and-conquer by looking based on where their name is alphabetically, and in every section you only need to explore a subset of each section before you eventually find someone's phone number.

: 예를들어, 사람들을 전화번호부에서 찾는 것이 O(log n)인 이유이다. 한 사람을 전화번호부에서 찾기위해 모든 사람을 체크할 필요없다. 대신에, 그들의 이름을 알파벳 순서로 찾아보는 분할정복(divide-and-conquer)을 사용할 수 있다, 그리고 어떤 사람의 전화번호를 찾기위해서 오직 각 섹션의 부분만 탐색할 필요가 있다. 

 

 

 

Of course, a bigger phone book will still take you a longer time, but it won't grow as quickly as the proportional increase in the additional size.

: 물론, 더 두꺼운 전화번호부는 찾는게 더 오랜시간이 걸릴 수 있지만, 걸리는 시간은 더 큰 크기만큼 비례하여 증가하지는 않는다. 

---

We can expand the phone book example to compare other kinds of operations and their running time. We will assume our phone book has businesses (the "Yellow Pages") which have unique names and people (the "White Pages") which may not have unique names. A phone number is assigned to at most one person or business. We will also assume that it takes constant time to flip to a specific page.

: 우리는 이 전화번호부의 예시를 다른 종류의 수행과 수행시간을 비교하는데 확장할 수 있다.  전화번호부에 고유한 이름을 가진 업체('옐로우 페이지')와 고유 이름이 없는 사람('화이트 페이지')이 있다고 가정한다. 전화번호는 최대 한 사람이나 사업체에 할당된다. 우리는 또한 특정한 페이지로 넘기는데(이동)에  O(1)이 걸린다고 가정한다. 

 

Here are the running times of some operations we might perform on the phone book, from fastest to slowest:

: 전화번호부에서 수행되는 특정 작업에 걸리는 시간을 빠른 순에서 느린 순으로 나열했다. 

 

O(1) (in the worst case): Given the page that a business's name is on and the business name, find the phone number. => 사업체의 이름이 적힌 페이지를 알고 있는 상태에서, 그 사업체의 전화번호를 찾는 것. 

 

O(1) (in the average case): Given the page that a person's name is on and their name, find the phone number.

=> 한 사람의 이름이 적힌 페이지를 알고 있는 상태에서, 그 사람의 전화번호를 찾는 것. 

 

O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.

=> 한 사람의 이름을 알고 있는 상태에서, 아직 찾아보지 않은 전화번호부의 반을 랜덤하게 집어 그 지점을 살펴보고 그 안에 그 사람의 이름이 있는지 찾아보는 것. 그 사람의 이름을 찾을 때 까지 같은 방식으로 계속 반복한다. 

 

O(n): Find all people whose phone numbers contain the digit "5".

=> 전화번호에 5가 들어가는 모든 사람들을 살펴보는 것. 

 

O(n): Given a phone number, find the person or business with that number.

=> 핸드폰 번호가 주어지고, 그 사람을 찾거나 사업체를 찾는 것. 

 

O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.

For the below examples, we're now at the printer's office. Phone books are waiting to be mailed to each resident or business, and there's a sticker on each phone book identifying where it should be mailed to. Every person or business gets one phone book.

=> 인쇄 업체의 실수로 전화번호부가 알파벳 순서로 정리되있지 않다. first name을 올바르게 찾기 위해서 각각 페이지의 순서를 고치고 빈 새로운 전화번호에 알맞은 위치에 넣는다. 위의 예시에서 우리는 인쇄소에 있다. 전화번호부가 각각 개인, 사업체에게 배송되기 위해 대기중이며, 그리고 각각 전화번호부에는 배송되어야하는 주소가 식별되는 스티커가 붙여있다. 결론적으로, 모든 개인과 사업체는 새롭게 정렬된 전화번호부를 받게 된다. 

 

 

O(log N) basically means time goes up linearly while the n goes up exponentially. So if it takes 1 second to compute 10 elements, it will take 2 seconds to compute 100 elements, 3 seconds to compute 1000 elements, and so on.

: O(log N)은 기본적으로 시간이 선형으로 증가하는 반면 n은 제곱배(지수)으로 증가하는 것을 의미한다. 따라서 10개의 요소를 계산하는 데 1초가 걸린다면 100개의 요소를 계산하는 데 2초, 1000개의 요소를 계산하는 데 3초가 걸린다.

 

​It is O(log n) when we do divide and conquer type of algorithms e.g binary search. Another example is quick sort where each time we divide the array into two parts and each time it takes O(N) time to find a pivot element. Hence it N O(log N)

: 우리가 이분 탐색(binary search)와 같은 divide and conquer 유형의 알고리즘을 구현할 때, O(logn)이다. 다른 예시는 "Quick Sort" 인데, Quick Sort는 배열을 두 파트로 나누고 중심(pivot)dmf 찾는데 O(N)이 걸린다. 

 

 

 

 

* More examples 

 

O(log(n)) - Logarithmic Examples:

• Algorithm 3 - This acts like "log_2"

Algorithm 3 demonstrates an algorithm that runs in log_2(n). Notice the post operation of the for loop multiples the current value of i by 2, so i goes from 1 to 2 to 4 to 8 to 16 to 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• Algorithm 4 - This acts like "log_3"

Algorithm 4 demonstrates log_3. Notice i goes from 1 to 3 to 9 to 27...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• Algorithm 5 - This acts like "log_1.02"

Algorithm 5 is important, as it helps show that as long as the number is greater than 1 and the result is repeatedly multiplied against itself, that you are looking at a logarithmic algorithm.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

 

 

 

 

 

 

 

 

 

 

reference : https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly