O (log n)는 정확히 무엇을 의미합니까?

time-complexity big-o


Big O Notation 실행 시간과 상각 시간에 대해 배우고 있습니다. O (n) 선형 시간 의 개념을 이해합니다 . 입력의 크기가 알고리즘의 성장에 비례하여 영향을 미치고 ... 예를 들어 2 차 시간 O (n 2 ) 등에도 동일하게 적용됩니다. (N (n!) 시간의 순열 생성기와 같이 계승에 의해 증가합니다.

예를 들어, 알고리즘이 입력 n 에 비례하여 증가하므로 다음 함수는 O (n)입니다 .

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

마찬가지로 중첩 루프가있는 경우 시간은 O (n 2 )입니다.

그러나 O (log n) 은 정확히 무엇 입니까? 예를 들어 완전한 이진 트리의 높이가 O (log n) 이라는 것은 무엇을 의미 합니까?

log 10 100 = 2 라는 의미에서 Logarithm이 무엇인지 알고 있지만 (상세하게는 아님) Logithmic Time으로 함수를 식별하는 방법을 이해할 수 없습니다.




Answer 1 John Feminella


로그 시간으로 함수를 식별하는 방법을 이해할 수 없습니다.

대수 실행 시간 함수의 가장 일반적인 속성은 다음과 같습니다.

  • 어떤 행동을 수행 할 다음 요소의 선택은 여러 가능성 중 하나이며,
  • 하나만 선택하면됩니다.

or

  • 조치가 수행되는 요소는 n의 숫자입니다.

예를 들어, 전화 번호부에서 사람을 찾는 것이 O (log n) 인 이유입니다. 전화 번호부의 모든 사람 을 확인하지 않아도 올바른 사람을 찾을 수 있습니다. 대신, 이름이 알파벳순으로 표시되어 구분하고 정복 할 수 있으며, 모든 섹션에서 누군가의 전화 번호를 찾기 전에 각 섹션의 하위 집합 만 탐색하면됩니다.

물론, 더 큰 전화 번호부는 여전히 시간이 오래 걸리지 만, 추가 크기가 비례 적으로 증가하는 것만 큼 빠르게 커지는 것은 아닙니다.


우리는 작업의 다른 종류와 비교하는 전화 번호부 예를 확장 할 수 있습니다 자신의 실행 시간을. 전화 번호부에 고유 한 이름을 가진 사업체 ( "노란색 페이지")와 고유 한 이름을 갖지 않는 사람들 ( "백색 페이지")이 있다고 가정합니다. 전화 번호는 최대 한 사람이나 회사에 할당됩니다. 또한 특정 페이지로 이동하는 데 일정한 시간이 걸린다고 가정합니다.

전화 번호부에서 수행 할 수있는 일부 작업의 실행 시간은 가장 빠르거나 느립니다.

  • O (1) (최악의 경우) : 업체 이름이있는 페이지와 업체 이름이 주어지면 전화 번호를 찾으십시오.

  • O (1) (평균적인 경우) : 사람의 이름이있는 페이지와 이름이 주어지면 전화 번호를 찾으십시오.

  • O (log n) : 사람의 이름이 주어지면 아직 검색하지 않은 책 부분의 중간 지점에서 임의의 지점을 선택한 다음 그 사람의 이름이 해당 지점에 있는지 확인하여 전화 번호를 찾습니다. 그런 다음 그 사람의 이름이있는 책 부분의 절반 정도에 대해 과정을 반복하십시오. (이것은 사람의 이름에 대한 이진 검색입니다.)

  • O (n) : 전화 번호에 숫자 "5"가 포함 된 모든 사람을 찾습니다.

  • O (n) : 전화 번호가 주어지면 해당 번호의 사람이나 업체를 찾습니다.

  • O (n log n) : 프린터 사무실에 혼동이 있었고 전화 번호부에 모든 페이지가 무작위로 삽입되었습니다. 각 페이지의 이름을 확인한 다음 새 빈 전화 번호부의 적절한 위치에 해당 페이지를 배치하여 순서가 올바른지 확인하십시오.

아래 예의 경우, 이제 프린터 사무실에 있습니다. 전화 번호부는 각 거주자 또는 사업자에게 우편으로 발송되기를 기다리고 있으며, 각 전화 번호부에 우편 발송 위치를 나타내는 스티커가 있습니다. 모든 사람이나 사업체는 전화 번호부를 하나받습니다.

  • O (n log n) : 전화 번호부를 개인화하고 싶기 때문에 지정된 사본에서 각 사람이나 회사 이름을 찾은 다음 책에서 이름을 동그라미로 표시하고 후원에 대한 짧은 감사의 글을 씁니다. .

  • 의 위에 2 ) : 사무실에서 실수가 발생했으며 각 전화 번호부의 모든 항목에는 전화 번호 끝에 "0"이 추가로 있습니다. 화이트 아웃을하고 각각의 0을 제거하십시오.

  • O (n · n!) : 전화 번호부를 배송 도크에로드 할 준비가되었습니다. 불행하게도, 책을로드해야했던 로봇은 완전히 사라졌습니다 : 책을 무작위 순서로 트럭에 싣고 있습니다! 더 나쁜 것은, 모든 서적을 트럭에 적재 한 다음, 올바른 순서인지 확인하고, 그렇지 않은 경우 적재를 해제하고 다시 시작하는 것입니다. (이것은 무서운 보고 정렬입니다 입니다.)

  • O (n n ) : 로봇이 올바르게 적재되도록 로봇을 고정시킵니다. 다음날 동료 중 한 명이 장난을 치고 로딩 독 로봇을 자동화 된 인쇄 시스템에 연결합니다. 로봇이 원본 책을로드 할 때마다 팩토리 프린터는 모든 전화 번호부를 중복 실행합니다! 다행스럽게도, 로봇의 버그 감지 시스템은 중복 된 책이 적재 될 때 로봇이 더 많은 사본을 인쇄하려고 시도하지 않지만 인쇄 된 모든 원본 및 복제 된 책을로드해야하는 정도로 정교합니다.




Answer 2 fastcodejava


O(log N) 기본적으로 시간이 선형으로 증가하고 n 이 기하 급수적 으로 증가 함을 의미 합니다. 따라서 10 개의 요소 를 계산 하는 데 1 초가 걸리면 100 개의 요소 를 계산하는 데 2 초 , 1000 을 계산하는 데 3 초가 걸립니다 요소 .

그것은이다 O(log n) 우리는 알고리즘 예를 들어, 이진 검색의 분할 및 정복 유형을 수행 할 때. 또 다른 예는 배열을 두 부분으로 나누고 피벗 요소를 찾는 데 O(N) 시간 이 걸리는 빠른 정렬 입니다. 따라서 N O(log N)




Answer 3 Jørn Schou-Rode


이 질문에 대한 많은 좋은 답변이 이미 게시되어 있지만 중요한 답변, 즉 설명 된 답변이 실제로 누락되었다고 생각합니다.

완전한 이진 트리의 높이가 O (log n)라는 것은 무엇을 의미합니까?

다음 그림은 이진 트리를 나타냅니다. 각 레벨에 위의 레벨에 비해 두 배의 노드 수가 어떻게 포함되는지 확인하십시오 (따라서 binary ).

Binary tree

이진 검색은 복잡도 O(log n) 입니다. 그림 1에서 트리의 맨 아래 레벨에있는 노드는 정렬 된 콜렉션의 항목을 나타냅니다. 이진 검색은 분할 및 정복 알고리즘이며이 그림은이 16 개의 항목 데이터 세트에서 검색중인 레코드를 찾기 위해 최대 4 개의 비교가 필요한 방법을 보여줍니다.

대신 32 개의 요소가있는 데이터 세트가 있다고 가정합니다. 데이터의 양을 곱할 때 트리가 한 단계 깊게 성장했기 때문에 검색 대상을 찾기 위해 5 개의 비교가 필요하다는 것을 알기 위해 위의 그림을 계속하십시오. 결과적으로 알고리즘의 복잡성을 로그 순서로 설명 할 수 있습니다.

일반 용지에 log(n) 을 플로팅 하면 n 이 증가함에 따라 곡선의 상승이 감속되는 그래프가 생성됩니다 .

O(log n)




Answer 4 2cupsOfTech


아래 설명은 완전 균형 이진 트리 의 경우를 사용하여 로그 시간 복잡성을 얻는 방법을 이해하는 데 도움이됩니다.

이진 트리는 크기 n의 문제를 크기 1의 문제에 도달 할 때까지 크기 n / 2의 하위 문제로 나누는 경우입니다.

height of a binary tree

그리고 이것이 당신이 솔루션에 도달하기 위해 위의 트리에서 수행해야 할 작업량 인 O (log n)을 얻는 방법입니다.

O (log n) 시간 복잡성을 갖는 일반적인 알고리즘은 재귀 관계가 T (n / 2) + O (1) 인 이진 검색입니다. 즉, 트리의 모든 후속 레벨에서 문제를 반으로 나누고 일정한 양의 추가 작업을 수행합니다.




Answer 5 James Oravec


Overview

다른 사람들은 트리 다이어그램과 같은 좋은 다이어그램 예제를 제공했습니다. 간단한 코드 예제는 보지 못했습니다. 따라서 내 설명 외에도 여러 알고리즘 범주의 복잡성을 설명하기 위해 간단한 인쇄 문이있는 알고리즘을 제공합니다.

먼저 https://en.wikipedia.org/wiki/Logarithm 에서 얻을 수있는 Logarithm에 대한 일반적인 아이디어가 필요합니다 . 자연 과학은 e 와 자연 로그를 사용합니다. 엔지니어링 제자는 log_10 (log base 10)을 사용하고 컴퓨터 과학자는 log_2 (log base 2)를 많이 사용합니다. 컴퓨터는 이진 기반이기 때문입니다. 때로는 자연 로그의 약어가 ln() 되며 엔지니어는 일반적으로 _10을 끄고 log() 하고 log_2는 lg() 로 약어로 표시됩니다 . 모든 유형의 로그는 비슷한 방식으로 커지므로 동일한 범주의 log(n) 을 공유합니다. .

아래 코드 예제를 볼 때 O (1), O (n), O (n ^ 2)를 확인하는 것이 좋습니다. 당신이 그것들을 잘 알고 나면 다른 것들을보십시오. 미묘한 변경으로 인해 동일한 분류가 어떻게 이루어질 수 있는지 보여주는 변형과 함께 깨끗한 예가 포함되어 있습니다.

O (1), O (n), O (logn) 등을 클래스 또는 성장 범주로 생각할 수 있습니다. 일부 카테고리는 다른 카테고리보다 시간이 더 걸립니다. 이 범주는 알고리즘 성능을 주문하는 방법을 제공합니다. 일부는 입력 n이 증가함에 따라 더 빠르게 성장했습니다. 하기 표는 상기 성장을 수치 적으로 설명한다. 아래 표에서 log (n)을 log_2의 상한값으로 생각하십시오.

enter image description here

다양한 Big O 카테고리의 간단한 코드 예제 :

O (1)-상수 시간 예 :

  • 알고리즘 1 :

알고리즘 1은 hello를 한 번 인쇄하고 n에 의존하지 않으므로 항상 일정한 시간에 실행되므로 O(1) 입니다.

print "hello";
  • 알고리즘 2 :

알고리즘 2는 hello를 3 번 ​​인쇄하지만 입력 크기에 의존하지 않습니다. n이 커지더라도이 알고리즘은 항상 hello를 3 번만 인쇄합니다. 3이라고하는 것은 상수이므로이 알고리즘도 O(1) 입니다.

print "hello";
print "hello";
print "hello";

O (log (n))-대수 예제 :

  • 알고리즘 3- "log_2"와 같은 역할

알고리즘 3은 log_2 (n)에서 실행되는 알고리즘을 보여줍니다. for 루프의 사후 연산은 i의 현재 값에 2를 곱하므로 i 32 16 8 4 2 1 간다 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • 알고리즘 4- "log_3"과 같은 기능

알고리즘 4는 log_3을 보여줍니다. 공지 사항 i 27 9 3 1에서 이동 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • 알고리즘 5- "log_1.02"와 같은 기능

알고리즘 5는 숫자가 1보다 크고 결과가 반복해서 자신에 대해 곱해지는 한, 로그 알고리즘을보고 있다는 것을 보여 주므로 중요합니다.

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

O (n)-선형 시간 예 :

  • 알고리즘 6

이 알고리즘은 간단하며 hello를 n 번 인쇄합니다.

for(int i = 0; i < n; i++)
  print "hello";
  • 알고리즘 7

이 알고리즘은 hello n / 2 번 인쇄되는 변형을 보여줍니다. n / 2 = 1/2 * n. 1/2 상수를 무시하고이 알고리즘이 O (n)임을 알 수 있습니다.

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n))-nlog (n) 예 :

  • 알고리즘 8

이것을 O(log(n))O(n) 의 조합으로 생각하십시오 . for 루프의 중첩은 O(n*log(n)) 얻는 데 도움이 됩니다.

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • 알고리즘 9

알고리즘 9는 알고리즘 8과 유사하지만 각 루프마다 변형이 허용되므로 최종 결과는 여전히 O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2)-n 제곱 예 :

  • 알고리즘 10

O(n^2) 표준 for 루프를 중첩하여 O (n ^ 2) 를 쉽게 얻을 수 있습니다.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • 알고리즘 11

알고리즘 10과 유사하지만 약간의 변형이 있습니다.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3)-n 큐브 형 예 :

  • 알고리즘 12

이것은 알고리즘 10과 비슷하지만 2 대신 3 개의 루프가 있습니다.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • 알고리즘 13

알고리즘 12와 유사하지만 여전히 변형이 O(n^3) 입니다.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Summary

위의 몇 가지 간단한 예와 분석을 변경하지 않는 미묘한 변경 사항을 소개 할 수있는 변형을 제시합니다. 잘만되면 그것은 당신에게 충분한 통찰력을 제공합니다.