질문자 :Andreas Grech
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) 이라는 것은 무엇을 의미합니까?
나는 log 10 100 = 2라는 의미에서 Logarithm이 무엇인지 알고(아주 자세히는 아니지만) logarithmic 시간으로 함수를 식별하는 방법을 이해할 수 없습니다.
로그 시간으로 기능을 식별하는 방법을 이해할 수 없습니다.
로그 실행 시간 함수의 가장 일반적인 속성은 다음과 같습니다.
- 어떤 행동을 수행할 다음 요소의 선택은 여러 가능성 중 하나이며,
- 하나만 선택하면 됩니다.
또는
이것이 예를 들어 전화번호부에서 사람을 찾는 것이 O(log n)인 이유입니다. 올바른 사람을 찾기 위해 전화번호부에 있는 모든 사람을 확인할 필요는 없습니다. 대신에, 당신은 단순히 그들의 이름이 알파벳순으로 있는 위치를 기반으로 하여 분할 정복할 수 있으며, 모든 섹션에서 누군가의 전화 번호를 찾기 전에 각 섹션의 하위 집합을 탐색하기만 하면 됩니다.
물론 더 큰 전화번호부는 여전히 더 오랜 시간이 걸리지만 추가 크기의 비례 증가만큼 빠르게 증가하지는 않습니다.
우리는 작업의 다른 종류와 그 실행 시간을 비교하기 위해 전화 번호부 예를 확장 할 수 있습니다. 전화번호부에 고유한 이름을 가진 비즈니스 ("옐로우 페이지")와 고유한 이름 이 없을 수 있는 사람 ("화이트 페이지")이 있다고 가정합니다. 전화번호는 최대 한 사람 또는 회사에 할당됩니다. 또한 특정 페이지로 넘어가는 데 일정한 시간이 걸린다고 가정합니다.
다음은 전화번호부에서 수행할 수 있는 몇 가지 작업의 실행 시간입니다. 가장 빠른 것부터 가장 느린 것까지:
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 ): 로봇이 물건을 올바르게 로드하도록 수정합니다. 다음 날, 동료 중 한 명이 당신에게 장난을 치고 로딩 도크 로봇을 자동 인쇄 시스템에 연결합니다. 로봇이 원본 책을 로드할 때마다 공장 프린터는 모든 전화번호부를 복제합니다! 다행히 로봇의 버그 감지 시스템은 로드할 중복 책을 발견했을 때 로봇이 더 많은 사본을 인쇄하려고 시도하지 않을 정도로 정교하지만 여전히 인쇄된 모든 원본과 중복 책을 로드해야 합니다.
O(log N) n 이 기하급수적으로 증가하는 동안 시간이 선형적으로 증가한다는 것을 의미합니다. 10 요소를 계산하는 데 1 100 요소를 계산하는 2 1000 요소를 계산하는 데 3 초가 걸리는 식입니다.
이진 검색과 같은 알고리즘 유형을 분할 정복할 때 O(log n) 또 다른 예는 배열을 두 부분으로 나눌 때마다 그리고 피벗 요소를 찾는 O(N) 따라서 NO(log N)
이 질문에 대한 많은 좋은 답변이 이미 게시되어 있지만, 저는 우리가 정말로 중요한 답변, 즉 그림이 있는 답변을 놓치고 있다고 생각합니다.
완전한 이진 트리의 높이가 O(log n)이라는 것은 무엇을 의미합니까?
다음 그림은 이진 트리를 나타냅니다. 각 레벨이 위의 레벨(따라서 바이너리 )과 비교하여 두 배의 노드 수를 포함하는 방법에 주목하십시오.
이진 검색은 복잡도가 O(log n) 입니다. 그림 1에서 트리의 맨 아래 수준에 있는 노드가 정렬된 컬렉션의 항목을 나타낸다고 가정해 보겠습니다. 이진 검색은 분할 정복 알고리즘이며 그림은 이 16개 항목 데이터 세트에서 검색 중인 레코드를 찾기 위해 (최대) 4번의 비교가 필요한 방법을 보여줍니다.
대신 32개의 요소가 있는 데이터 세트가 있다고 가정합니다. 위의 그림을 계속 진행하면 데이터 양을 곱할 때 트리가 한 단계 더 깊어지기 때문에 찾고 있는 것을 찾기 위해 5번의 비교가 필요하다는 것을 알 수 있습니다. 결과적으로 알고리즘의 복잡성은 로그 차수로 설명할 수 있습니다.
log(n) 을 플로팅 n 증가함에 따라 곡선의 상승이 감속하는 그래프가 생성됩니다.
아래 설명은 대수 시간 복잡도를 얻는 방법을 이해하는 데 도움이 되도록 완전히 균형 잡힌 이진 트리의 경우를 사용합니다.
이진 트리는 크기 n의 문제가 크기 1의 문제에 도달할 때까지 크기 n/2의 하위 문제로 분할되는 경우입니다.
그리고 이것이 솔루션에 도달하기 위해 위의 트리에서 수행해야 하는 작업의 양인 O(log n)을 얻는 방법입니다.
O(log n) 시간 복잡도를 가진 일반적인 알고리즘은 재귀 관계가 T(n/2) + O(1)인 이진 검색입니다. 즉, 트리의 모든 후속 수준에서 문제를 절반으로 나누고 일정한 양의 추가 작업을 수행합니다.
개요
다른 사람들은 트리 다이어그램과 같은 좋은 다이어그램 예제를 제공했습니다. 간단한 코드 예제는 보지 못했습니다. 따라서 내 설명과 함께 다양한 알고리즘 범주의 복잡성을 설명하기 위해 간단한 인쇄 문으로 몇 가지 알고리즘을 제공하겠습니다.
먼저 https://en.wikipedia.org/wiki/Logarithm 에서 얻을 수 있는 Logarithm에 대한 일반적인 아이디어가 필요합니다. 자연 과학은 e 와 자연 로그를 사용합니다. 컴퓨터가 바이너리 기반이기 때문에 공학 제자들은 log_10(로그 기반 10)을 사용하고 컴퓨터 과학자들은 log_2(로그 기반 2)를 많이 사용할 것입니다. 때로는 자연 로그의 약어를 ln() 있으며 엔지니어는 일반적으로 _10 을 생략하고 log() lg() 로 축약합니다. 모든 유형의 로그는 비슷한 방식으로 성장하므로 동일한 범주의 log(n) 을 공유합니다.
아래 코드 예제를 볼 때 O(1), O(n), O(n^2) 순으로 살펴보는 것이 좋습니다. 당신이 그것들을 잘한 후에 다른 것을 보라. 나는 미묘한 변화가 어떻게 여전히 동일한 분류를 초래할 수 있는지 보여주기 위해 깨끗한 예와 변형을 포함했습니다.
O(1), O(n), O(logn) 등을 성장의 클래스 또는 범주로 생각할 수 있습니다. 일부 범주는 다른 범주보다 수행하는 데 더 많은 시간이 걸립니다. 이러한 범주는 알고리즘 성능을 정렬하는 방법을 제공하는 데 도움이 됩니다. 일부는 입력 n이 증가함에 따라 더 빠르게 성장했습니다. 다음 표는 상기 성장을 수치적으로 보여줍니다. 아래 표에서 log(n)을 log_2의 상한으로 생각하십시오.
다양한 Big O 카테고리의 간단한 코드 예:
O(1) - 일정 시간 예:
알고리즘 1은 hello를 한 번 인쇄하고 n에 의존하지 않으므로 항상 일정한 시간에 실행되므로 O(1) 입니다.
print "hello";
알고리즘 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 는 1에서 2, 4, 8, 16, 32가 됩니다.
for(int i = 1; i <= n; i = i * 2) print "hello";
- 알고리즘 4 - "log_3"처럼 작동합니다.
알고리즘 4는 log_3을 보여줍니다. i 는 1에서 3으로, 9에서 27로 이동합니다...
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) - 선형 시간 예:
이 알고리즘은 간단하며 hello를 n번 인쇄합니다.
for(int i = 0; i < n; i++) print "hello";
이 알고리즘은 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) 예:
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는 알고리즘 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 제곱 예:
O(n^2) 는 표준 for 루프를 중첩하여 쉽게 얻을 수 있습니다.
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) print "hello";
알고리즘 10과 비슷하지만 약간의 변형이 있습니다.
for(int i = 0; i < n; i++) for(int j = 0; j < n; j = j + 2) print "hello";
O(n^3) - n 세제곱 예:
이것은 알고리즘 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";
알고리즘 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";
요약
위의 몇 가지 간단한 예와 실제로 분석을 변경하지 않는 미묘한 변경이 도입될 수 있음을 보여주는 변형을 제공합니다. 충분한 통찰력을 제공하기를 바랍니다.
다음을 수행하는 함수가 있는 경우:
1 millisecond to complete if you have 2 elements. 2 milliseconds to complete if you have 4 elements. 3 milliseconds to complete if you have 8 elements. 4 milliseconds to complete if you have 16 elements. ... n milliseconds to complete if you have 2^n elements.
그런 다음 로그 2 (n) 시간이 걸립니다. 느슨하게 말하면 Big O 표기법 은 관계가 큰 n에 대해서만 참이면 되며 상수 요인과 더 작은 항은 무시할 수 있음을 의미합니다.
로그
자, 로그가 실제로 무엇인지 완전히 이해하려고 노력해 봅시다.
우리에게 밧줄이 있고 그것을 말에 묶었다고 상상해 보십시오. 밧줄이 말에 직접 묶인 경우 말이 당기는 데 필요한 힘(예: 사람에게서)은 직접 1입니다.
이제 밧줄이 기둥 주위에 고리가 있다고 상상해보십시오. 도망치려는 말은 이제 몇 배나 더 세게 당겨야 합니다. 횟수는 로프의 거칠기와 장대의 크기에 따라 다르지만, 자신의 힘이 10배(로프가 완전히 회전할 때)한다고 가정해 봅시다.
이제 로프가 한 번만 반복되면 말은 10배 더 세게 당겨야 합니다. 사람이 말을 어렵게 만들기로 결정하면 밧줄을 장대에 다시 감아 강도를 10배 더 높일 수 있습니다. 세 번째 루프는 다시 강도를 10배 더 증가시킵니다.
각 루프에 대해 값이 10씩 증가하는 것을 볼 수 있습니다. 임의의 숫자를 얻는 데 필요한 회전 수를 숫자의 로그라고 합니다. 즉, 힘을 1000배로 곱하려면 3개의 포스트가 필요하고 힘을 곱하려면 6개의 포스트가 필요합니다. 1,000,000
3은 1,000의 로그이고 6은 1,000,000의 로그입니다(밑수 10).
그렇다면 O(log n)은 실제로 무엇을 의미합니까?
위의 예에서 '성장률'은 O(log n) 입니다. 루프가 추가될 때마다 로프가 처리할 수 있는 힘은 10배 더 커집니다.
Turns | Max Force 0 | 1 1 | 10 2 | 100 3 | 1000 4 | 10000 n | 10^n
이제 위의 예는 기수 10을 사용했지만 다행스럽게도 빅오 표기법에 대해 이야기할 때 로그의 기수는 중요하지 않습니다.
이제 1-100 사이의 숫자를 추측하려고 한다고 가정해 보겠습니다.
Your Friend: Guess my number between 1-100! Your Guess: 50 Your Friend: Lower! Your Guess: 25 Your Friend: Lower! Your Guess: 13 Your Friend: Higher! Your Guess: 19 Your Friend: Higher! Your Friend: 22 Your Guess: Lower! Your Guess: 20 Your Friend: Higher! Your Guess: 21 Your Friend: YOU GOT IT!
이제 이것을 맞추는 데 7개의 추측이 필요했습니다. 그런데 여기서 어떤 관계가 있습니까? 각 추가 추측에서 추측할 수 있는 항목의 최대량은 무엇입니까?
Guesses | Items 1 | 2 2 | 4 3 | 8 4 | 16 5 | 32 6 | 64 7 | 128 10 | 1024
그래프를 사용하여 이진 검색을 사용하여 1-100 사이의 숫자를 추측하는 경우 최대 7번의 시도가 필요함을 알 수 있습니다. 128개의 숫자가 있는 경우 7번의 시도로 숫자를 추측할 수도 있지만 129개의 숫자는 최대 8번의 시도가 필요합니다. 7은 128의 로그, 10은 1024의 로그(밑 2)입니다.
내가 '대부분'으로 굵게 표시한 것에 주목하십시오. Big-O 표기법은 항상 더 나쁜 경우를 나타냅니다. 운이 좋다면 한 번에 숫자를 추측할 수 있으므로 가장 좋은 경우는 O(1)이지만 이는 다른 이야기입니다.
추측할 때마다 데이터 세트가 줄어들고 있음을 알 수 있습니다. 알고리즘에 대수 시간이 있는지 식별하는 좋은 경험 법칙은 각 반복 후에 데이터 세트가 특정 순서로 축소되는지 확인하는 것입니다.
O(n log n)은 어떻습니까?
결국 선형 시간 O(n log(n)) 알고리즘을 보게 될 것입니다. 어림짐작 위에 다시 적용되지만 대수 함수를 갖는다 이번에 실행 n 번 예는 머지 소트 등의 알고리즘에서 발생하는 시간에서 N의 크기를 감소시킨다.
알고리즘 시간이 n log n인지 쉽게 식별할 수 있습니다. 목록을 반복하는 외부 루프를 찾습니다(O(n)). 그런 다음 내부 루프가 있는지 확인하십시오. 내부 루프가 각 반복에서 데이터 세트를 잘라내거나 줄이는 경우 해당 루프는 (O(log n))이므로 전체 알고리즘은 = O(n log n) 입니다.
면책 조항: 로프 로그 예제는 W.Sawyer의 뛰어난 Mathematician's Delight 책에서 가져왔습니다 .
대수 실행 시간( O(log n) )은 본질적으로 실행 시간이 입력 크기의 대수 에 비례하여 증가한다는 것을 의미합니다. 예를 들어, 10개 항목이 최대 어느 정도 시간 x 가 걸리고 100개 항목이 최대 시간이 걸리는 경우, 예를 들어 2x , 10,000개 항목은 최대 4x O(log n) 시간 복잡도처럼 보입니다.
먼저 다음 책을 읽을 것을 권장합니다.
알고리즘(4판)
다음은 몇 가지 기능과 예상되는 복잡성입니다. 숫자는 명령문 실행 빈도를 나타냅니다.
Bigoheatsheet 에서 가져온 Big-O Complexity Chart에 따라 
마지막으로 매우 간단한 쇼케이스가 계산 방법을 보여줍니다.
프로그램의 명령문 실행 빈도 분석.
프로그램의 실행 시간 분석(예시).
시간은 N의 자릿수에 비례한다고 하여 직관적으로 O(log N)을 생각할 수 있습니다.
연산이 입력의 각 자릿수 또는 비트에 대해 일정한 시간 작업을 수행하는 경우 전체 연산은 입력의 크기가 아니라 입력의 자릿수 또는 비트 수에 비례하는 시간이 걸립니다. 따라서 O(N)보다는 O(log N)입니다.
연산이 고려되는 입력의 크기를 반으로 줄이는 일련의 일정한 시간 결정(3, 4, 5..만큼 감소)을 내리는 경우 전체는 로그 밑 2(밑 3 , 밑수 4, 밑수 5...) 입력의 크기 N이 아니라 O(N)입니다.
등등.
O(log n)에서 실행되는 알고리즘을 항상 정신적으로 시각화해야 했던 가장 좋은 방법은 다음과 같습니다.
문제 크기를 곱한 양만큼 늘리면(즉, 크기에 10을 곱하면) 작업은 더하는 양만큼만 증가합니다.
이것을 이진 트리 질문에 적용하면 좋은 적용이 됩니다. 이진 트리의 노드 수를 두 배로 늘리면 높이는 1(추가량)만 증가합니다. 다시 두 배로 늘리면 여전히 1 만 증가합니다. (분명히 균형을 유지한다고 가정합니다). 그렇게 하면 문제 크기가 배가될 때 작업을 두 배로 늘리는 대신 아주 약간만 더 많은 작업을 수행하게 됩니다. 이것이 O(log n) 알고리즘이 멋진 이유입니다.
로그 b (n)는 무엇입니까?
크기가 1인 단면에 도달하기 전에 길이가 n인 로그를 b 등분으로 반복해서자를 수 있는 횟수입니다.
분할 정복 알고리즘에는 일반적으로 logn 구성 요소가 있습니다. 이것은 입력의 반복적인 반감에서 비롯됩니다.
이진 검색의 경우 반복할 때마다 입력의 절반을 버립니다. Big-O 표기법에서 log는 log base 2라는 점에 유의해야 합니다.
편집: 언급했듯이 로그 기반은 중요하지 않지만 알고리즘의 Big-O 성능을 도출할 때 로그 요소는 반감에서 나오므로 기본 2로 생각하는 이유입니다.
그러나 O(log n)은 정확히 무엇입니까? 예를 들어, >완전한 이진 트리의 높이가 O(log n)이라는 것은 무엇을 의미합니까?
나는 이것을 '완전한 이진 트리의 높이는 log n'이라고 바꾸어 말할 것입니다. 전체 이진 트리의 높이를 계산하는 것은 단계적으로 아래로 이동하는 경우 O(log n)이 됩니다.
로그 시간으로 함수를 식별하는 방법을 이해할 수 없습니다.
로그는 본질적으로 지수의 역수입니다. 함수 각각 '단계'는 원본 항목 세트의 요소의 요소를 제거되고 경우에 따라서, 즉 시간 대수 알고리즘이다.
트리 예제의 경우 노드 수준을 낮추면 탐색을 계속할 때 요소 수가 기하급수적으로 감소한다는 것을 쉽게 알 수 있습니다. 이름으로 정렬된 전화번호부를 살펴보는 인기 있는 예는 본질적으로 이진 검색 트리를 탐색하는 것과 동일합니다(중간 페이지는 루트 요소이며 각 단계에서 왼쪽 또는 오른쪽으로 이동할지 추론할 수 있습니다).
O(log n)은 약간 오해의 소지가 있습니다. 더 정확하게는 O(log 2 n), 즉 (밑이 2인 로그)입니다.
균형 이진 트리의 높이는 O(log 2 n)입니다. 모든 노드에는 2개의 자식 노드( log 2 n에서와 같이 "2")가 있기 때문입니다. 따라서, n 개의 노드가있는 트리 로그 2 N의 높이를 가지고있다.
또 다른 예는 실행 시간이 O(log 2 n)인 이진 검색입니다. 모든 단계에서 검색 공간을 2로 나누기 때문입니다.
이 2가지 경우는 O(log n) 시간이 걸립니다.
case 1: f(int n) { int i; for (i = 1; i < n; i=i*2) printf("%d", i); } case 2 : f(int n) { int i; for (i = n; i>=1 ; i=i/2) printf("%d", i); }
이것은 단순히 이 작업에 필요한 시간이 log(n)과 함께 증가한다는 것을 의미합니다(예: n = 10의 경우 2초, n = 100의 경우 4초, ...). 이진 검색 알고리즘 및 Big O 표기법에 대한 Wikipedia 기사를 읽어보세요.
O(log n) 은 대수(대부분의 경우 일반적으로 밑이 2이지만 항상 그런 것은 아니며 어떤 경우에도 큰 값에 의해 중요하지 않음)에 비례하는 시간 동안 작동하는 함수(또는 알고리즘 또는 알고리즘의 단계)를 나타냅니다 -O 표기법*) 입력 크기.
로그 함수는 지수 함수의 역함수입니다. 다시 말해 입력이 기하급수적으로 증가하면(일반적으로 생각하는 선형이 아닌) 함수가 선형으로 증가합니다.
O(log n) 실행 시간은 모든 종류의 분할 정복 응용 프로그램에서 매우 일반적입니다. 왜냐하면 (이상적으로는) 매번 작업을 절반으로 줄이기 때문입니다. 각 나눗셈 또는 정복 단계에서 일정한 시간 작업(또는 일정 시간이 아니지만 시간이 O(log n) 보다 느리게 증가하는 작업)을 수행하는 경우 전체 함수는 O(log n) . 대신 각 단계에 입력에 선형 시간이 필요하도록 하는 것이 일반적입니다. O(n log n) 의 총 시간 복잡도에 해당합니다.
이진 검색의 실행 시간 복잡도는 O(log n) 의 예입니다. 이것은 이진 검색에서 배열을 반으로 나누고 각 단계에서 절반에만 집중하여 각 이후 단계에서 입력의 절반을 항상 무시하기 때문입니다. 각 단계는 일정 시간입니다. 왜냐하면 바이너리 검색에서는 고려 중인 배열이 어느 시점에서 얼마나 큰지에 관계없이 다음에 무엇을 해야 하는지 알아내기 위해 하나의 요소만 키와 비교하면 되기 때문입니다. 따라서 대략적으로 log(n)/log(2) 단계를 수행합니다.
병합 정렬의 실행 시간 복잡도는 O(n log n) 의 예입니다. 이는 각 단계에서 어레이를 반으로 나누어 총 대략 log(n)/log(2) 단계가 되기 때문입니다. 그러나 각 단계에서 모든 요소에 대해 병합 작업을 수행해야 합니다. 각 단계에서 n개의 요소에 대해 이 작업을 수행합니다. 따라서 총 복잡도는 O(n log n) 입니다.
* big-O 표기법 은 정의에 따라 상수가 중요하지 않다는 것을 기억하십시오. 또한 로그에 대한 기본 규칙 의 변경으로 인해 다른 밑의 로그 간의 유일한 차이는 상수 요인입니다.
간단히 말해서 알고리즘의 각 단계에서 작업을 반으로 줄일 수 있습니다. (점근적으로 세 번째, 네 번째, ...)
그래픽 계산기 또는 이와 유사한 것으로 로그 함수를 플롯하면 선형 함수보다 훨씬 느리게 상승하는 것을 볼 수 있습니다.
이것이 대수 시간 복잡도를 가진 알고리즘이 많이 찾는 이유입니다. 실제로 큰 n(예를 들어 n = 10^8이라고 가정해 봅시다)의 경우에도 허용 가능한 것 이상으로 성능을 발휘합니다.
그러나 정확히 O(log n)은 무엇입니까?
정확히 의미하는 바는 " n 이 infinity time a*log(n) 향하는 경향이 있으며 여기서 a 는 일정한 배율 인수"입니다.
또는 실제로 그것이 의미하는 바는 아닙니다. time a*log(n) 으로 나눈 값은 1 향하는 경향이 있습니다"와 같은 의미일 가능성이 더 큽니다.
당신이 어떤 임의의 작은 영이 아닌 상수를 선택하는 경우, 예를 들어, "즉, '분석'에서 일반적인 수학적 의미가있다"쪽으로 경향이있다 " k , 그때는 해당 값을 찾을 수 있습니다 X 같은 그 ((time/(a*log(n))) - 1) 은 X n 모든 값에 대해 k 보다 작습니다."
간단히 말해서 시간 방정식에는 몇 가지 다른 구성 요소가 있을 수 있음을 의미합니다. 예를 들어 일정한 시작 시간이 있을 수 있습니다. 그러나 이러한 다른 구성 요소는 n의 큰 값에 대해 무의미하고, a*log(n)은 큰 n에 대한 지배적인 용어입니다.
방정식이 예를 들어 ...
시간(n) = a + b log(n) + c n + d n n
... 그러면 이것은 O(n 제곱)이 될 것입니다. 왜냐하면 상수 a, b, c 및 0이 아닌 d의 값이 무엇이든 상관없이 d*n*n 항은 충분한 기간 동안 항상 다른 항보다 우세하기 때문입니다. n의 큰 값.
이것이 비트 O 표기법이 의미하는 것입니다. "충분히 큰 n에 대한 지배적 항의 순서는 무엇입니까"를 의미합니다.
나는 오래전에 Kormen 등의 책에서 읽은 흥미로운 것을 추가할 수 있습니다. 이제 문제 공간에서 솔루션을 찾아야 하는 문제를 상상해 보십시오. 이 문제 공간은 유한해야 합니다.
이제 알고리즘을 반복할 때마다 이 공간의 일부를 잘라냈다는 것을 증명할 수 있다면, 이는 어떤 제한보다 작지 않으며, 이는 알고리즘이 O(logN) 시간에 실행되고 있음을 의미합니다.
나는 여기서 우리가 절대적인 것이 아니라 상대적인 분수 한계에 대해 이야기하고 있다는 점을 지적해야 합니다. 이진 검색은 고전적인 예입니다. 각 단계에서 문제 공간의 1/2을 버립니다. 그러나 이진 검색이 유일한 예는 아닙니다. 각 단계에서 문제 공간의 최소 1/128을 버린다는 것을 어떻게든 증명했다고 가정합니다. 즉, 바이너리 검색보다 훨씬 느리지만 프로그램이 여전히 O(logN) 시간에 실행되고 있습니다. 이것은 재귀 알고리즘을 분석하는 데 아주 좋은 힌트입니다. 각 단계에서 재귀가 여러 변형을 사용하지 않는다는 것이 종종 증명될 수 있으며, 이로 인해 문제 공간에서 일부 분수가 차단됩니다.
알고리즘이나 코드를 작성할 때마다 점근적 복잡성을 분석하려고 합니다. 시간 복잡도 와 다릅니다.
점근적 복잡도는 알고리즘의 실행 시간 동작이고 시간 복잡도는 실제 실행 시간입니다. 그러나 어떤 사람들은 이 용어를 같은 의미로 사용합니다.
시간 복잡도는 다양한 매개변수에 따라 달라집니다.
1. 물리적 시스템
2. 프로그래밍 언어
3. 코딩 스타일
4. 그리고 훨씬 더 ......
실제 실행 시간은 분석을 위한 좋은 척도가 아닙니다.
대신 코드가 무엇이든 입력이 동일하기 때문에 입력 크기를 매개변수로 사용합니다. 따라서 실행 시간은 입력 크기의 함수입니다.
다음은 선형 시간 알고리즘의 예입니다.
선형 검색
n개의 입력 요소가 주어지면 배열에서 요소를 검색하려면 최대 'n'개의 비교 가 필요합니다. 즉, 어떤 프로그래밍 언어를 사용하든, 어떤 코딩 스타일을 선호하든, 어떤 시스템에서 실행하든 상관 없습니다. 최악의 시나리오에서는 n개의 비교만 필요합니다. 실행 시간은 입력 크기에 선형적으로 비례합니다.
검색뿐만 아니라 작업(증가, 비교 또는 모든 작업)이 무엇이든 입력 크기의 함수입니다.
따라서 어떤 알고리즘이 O(log n)이라고 말하면 실행 시간은 입력 크기 n의 log 곱을 의미합니다.
입력 크기가 커질수록 수행한 작업(여기서는 실행 시간)이 증가합니다.(따라서 비례)
n Work 2 1 units of work 4 2 units of work 8 3 units of work
입력 크기가 증가함에 따라 수행된 작업이 증가하고 어떤 기계와도 무관합니다. 그리고 만약 당신이 일의 단위의 가치를 알아내려고 하면 그것은 실제로 위에 명시된 매개변수에 의존합니다. 그것은 시스템과 모든 것에 따라 변할 것입니다.
for 루프에 대한 예를 들 수 있으며, 한 번 개념을 파악하면 다른 컨텍스트에서 이해하는 것이 더 간단할 수 있습니다.
즉, 루프에서 단계가 기하급수적으로 증가합니다. 예
for (i=1; i<=n; i=i*2) {;}
이 프로그램의 O 표기법의 복잡성은 O(log(n))입니다. 손으로 반복해 보겠습니다(n은 512와 1023 사이(1024 제외)):
step: 1 2 3 4 5 6 7 8 9 10 i: 1 2 4 8 16 32 64 128 256 512
n이 512와 1023 사이에 있지만 10번의 반복만 발생합니다. 이는 루프의 단계가 기하급수적으로 증가하므로 종료에 도달하는 데 10번만 반복하면 되기 때문입니다.
x의 로그(a의 밑)는 a^x의 역함수입니다.
로그는 지수의 역수라고 말하는 것과 같습니다.
이제 지수가 매우 빠르게 성장하면 로그가 (역으로) 매우 느리게 성장합니다.
O(n)과 O(log(n))의 차이는 O(n)과 O(a^n)(a는 상수임)의 차이와 유사하게 매우 큽니다.
실제로, n개의 요소 목록이 있고 해당 목록에서 이진 트리를 생성하는 경우(예: 분할 정복 알고리즘) 크기가 1인 목록(잎)에 도달할 때까지 계속 2로 나눕니다.
첫 번째 단계에서 2로 나눕니다. 그런 다음 2개의 목록(2^1)이 있고 각각을 2로 나누므로 4개의 목록(2^2)이 있고 다시 나누면 8개의 목록(2^3)이 있습니다. ) 목록 크기가 1이 될 때까지 계속
그것은 당신에게 방정식을 제공합니다 :
n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps
(각 변의 lg를 취합니다. lg는 로그 밑이 2입니다)
검색이 다음과 같기 때문에 완전한 이진 예제는 O(ln n)입니다.
1 2 3 4 5 6 7 8 9 10 11 12
4를 검색하면 3개의 적중이 나옵니다. 6, 3, 4. 그리고 log2 12 = 3입니다. 이는 필요한 곳에 얼마나 많은 적중이 있는지에 대한 좋은 근사치입니다.
log x to base b = y b^y = x 의 역수입니다.
깊이가 d이고 크기가 n인 M-ary 트리가 있는 경우:
정보 기술에서는 다음을 의미합니다.
f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, such that for all N>N0 "C*g(n) > f(n) > 0" is true.
개미 이 표기법은 대부분 수학에서 가져온 것 같습니다.
이 기사에는 DE Knuth, "BIG OMICRON AND BIG OMEGA AND BIG THETA", 1976년 인용문이 있습니다.
여기에서 논의된 문제를 기반으로 SIGACT 회원, 컴퓨터 과학 및 수학 저널 편집인이 더 나은 대안을 합리적으로 빨리 찾을 수 없는 한 위에서 정의한 표기법을 채택할 것을 제안합니다.
오늘은 2016년이지만 오늘날에도 여전히 사용하고 있습니다.
수학적 분석에서는 다음을 의미합니다.
lim (f(n)/g(n))=Constant; where n goes to +infinity
그러나 수학적 분석에서도 때때로 이 기호는 "C*g(n) > f(n) > 0"을 의미하는 데 사용되었습니다.
내가 대학에서 알고 있듯이 기호는 독일 수학자 Landau(1877-1938)에 의해 도입되었습니다.
직관 기반 답변을 찾고 있다면 두 가지 해석을 제시하고 싶습니다.
매우 넓은 기지와 함께 매우 높은 언덕도 상상해 보십시오. 언덕 꼭대기에 도달하는 방법은 두 가지가 있습니다. 하나는 정상에 도달하는 언덕 주위를 나선형으로 도는 전용 통로이고 다른 하나는 계단을 제공하기 위해 잘라낸 조각 같은 작은 테라스입니다. 이제 첫 번째 방법이 선형 시간 O(n)에 도달하는 경우 두 번째 방법은 O(log n)입니다.
정수를 허용하는 알고리즘을 상상 n 에 시간 비례 입력 완료로 n 은 O (N) 또는 세타 (N)는 다음하지만 시간 비율에서 실행되는 경우 number of digits or the number of bits in the binary representation on number 경우 알고리즘은 O(log n) 또는 세타(log n) 시간에 실행됩니다.
O(logn)은 모든 코드의 런타임 성능을 측정하는 다항식 시간 복잡도 중 하나입니다.
이진 검색 알고리즘에 대해 이미 들어보셨기를 바랍니다.
크기가 N인 배열에서 요소를 찾아야 한다고 가정해 보겠습니다.
기본적으로 코드 실행은 N N/2 N/4 N/8....등과 같습니다.
각 수준에서 수행한 모든 작업을 합산하면 n(1+1/2+1/4....)이 되고 O(logn)과 같습니다.
출처 : http:www.stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly