개발관련/other

O (log n)가 의미하는 것

Rateye 2021. 7. 21. 10:44
728x90
반응형
질문 : O (log n)는 정확히 무엇을 의미합니까?

Big O Notation 실행 시간과 상각 시간에 대해 배우고 있습니다. 나는 O (n) 선형 시간의 개념을 이해하는데, 이는 입력의 크기가 비례 적으로 알고리즘의 성장에 영향을 미친다는 것을 의미하며, 예를 들어 2 차 시간 O (n 2 ) 등과 같은 알고리즘도 마찬가지입니다. 계승에 의해 증가하는 순열 생성기와 같은 O (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) 라는 것은 무엇을 의미합니까?

나는 Logarithm이 무엇인지 알고 있습니다. (아마도 자세히는 아니지만) log 10 100 = 2라는 의미에서 로그가 무엇인지 알고 있지만 로그 시간으로 함수를 식별하는 방법을 이해할 수 없습니다.

답변

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

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

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

또는

  • 작업이 수행되는 요소는 n의 숫자입니다.

예를 들어 전화 번호부에서 사람을 찾는 것이 O (log n) 인 이유입니다. 전화 번호부의 모든 사람을 확인하여 올바른 사람을 찾을 필요는 없습니다. 대신 이름이 알파벳순으로 검색하여 간단히 나누고 정복 할 수 있으며, 모든 섹션에서 결국 누군가의 전화 번호를 찾기 전에 각 섹션의 하위 집합 만 탐색하면됩니다.

물론 전화 번호부 크기가 클수록 시간이 더 오래 걸리지 만 추가 크기의 비례 증가만큼 빠르게 증가하지는 않습니다.

우리는 작업의 다른 종류와 실행 시간을 비교하기 위해 전화 번호부 예를 확장 할 수 있습니다. 전화 번호부에 고유 한 이름을 가진 사업체 ( "Yellow Pages")와 고유 한 이름이없는 사람 ( "White Pages")이 있다고 가정합니다. 전화 번호는 최대 한 사람 또는 회사에 할당됩니다. 또한 특정 페이지로 넘기는 데 일정한 시간이 걸린다고 가정합니다.

전화 번호부에서 수행 할 수있는 일부 작업의 실행 시간은 다음과 같습니다.

  • O (1) (최악의 경우) : 업체 이름과 업체 이름이있는 페이지가 주어지면 전화 번호를 찾습니다.
  • O (1) (일반적인 경우) : 사람의 이름과 이름이있는 페이지가 주어지면 전화 번호를 찾습니다.
  • O (log n) : 사람의 이름이 주어지면 책에서 아직 검색하지 않은 부분의 중간 쯤에 임의의 지점을 선택한 다음 그 사람의 이름이 그 지점에 있는지 확인하여 전화 번호를 찾습니다. 그런 다음 그 사람의 이름이있는 책의 절반 쯤에 과정을 반복합니다. (이것은 사람의 이름에 대한 이진 검색입니다.)
  • O (n) : 전화 번호에 숫자 "5"가 포함 된 모든 사람을 찾습니다.
  • O (n) : 전화 번호가 주어지면 해당 번호로 사람이나 회사를 찾습니다.
  • O (n log n) : 프린터 사무실에 혼동이 있었고 전화 번호부에 모든 페이지가 무작위로 삽입되었습니다. 각 페이지의 이름을 확인한 다음 비어있는 새 전화 번호부의 적절한 위치에 해당 페이지를 배치하여 순서가 정확하도록 수정하십시오.

 

 

아래 예의 경우 현재 프린터 사무실에 있습니다. 전화 번호부는 각 거주자 나 회사로 발송되기를 기다리고 있으며, 각 전화 번호부에는 어디로 발송해야하는지 식별하는 스티커가 있습니다. 모든 사람이나 기업은 하나의 전화 번호부를받습니다.

  • O (n log n) : 우리는 전화 번호부를 개인화하고 싶으므로 지정된 사본에서 각 개인 또는 업체 이름을 찾은 다음 책에서 이름에 동그라미를 치고 후원에 대한 짧은 감사 메모를 작성합니다. .
  • O (n 2 ) : 사무실에서 실수가 발생했으며 각 전화 번호부의 모든 항목에는 전화 번호 끝에 추가 "0"이 있습니다. 약간의 화이트 아웃을 취하고 각각의 0을 제거하십시오.
  • O (n · n!) : 전화 번호부를 배송 도크에로드 할 준비가되었습니다. 안타깝게도 책을 실어야했던 로봇은 혼란스러워졌습니다. 책을 무작위 순서로 트럭에 올려 놓고 있습니다! 더 나쁜 것은 모든 책을 트럭에 실은 다음 올바른 순서로되어 있는지 확인하고, 그렇지 않은 경우에는 책을 내리고 다시 시작합니다. (이것은 두려운 보고 종류 입니다.)
  • O (n n ) : 로봇이 올바르게로드되도록 로봇을 고정합니다. 다음날 동료 중 한 명이 장난을 치며 로딩 도크 로봇을 자동화 된 인쇄 시스템에 연결합니다. 로봇이 원본 책을로드 할 때마다 공장 프린터가 모든 전화 번호부를 복제합니다! 다행히도 로봇의 버그 감지 시스템은 로봇이로드 할 중복 책을 발견했을 때 더 많은 사본을 인쇄하지 않을만큼 정교하지만, 인쇄 된 모든 원본과 중복 책을로드해야합니다.

 

 

출처 : https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly
728x90
반응형