o (log n)는 정확히 무엇을 의미합니까?
질문
나는 큰 o 표기법 실행 시간과 상각 시간을 배우고 있습니다.I (n) 선형 시간의 개념을 이해합니다. 즉, 입력의 크기가 알고리즘의 성장에 비례하여 알고리즘의 성장에 영향을 미치는 것으로, 예를 들어, 2 차 시간 O (N2) 등에 대해서도, 동일한 알고리즘,순열 발생기, o (n!) 시간, 계승에 의해 자라는 것.
예를 들어 알고리즘이 입력 N에 비례하여 성장하기 때문에 다음 기능은 o (n)입니다.
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
마찬가지로 중첩 루프가 있으면 시간은 O (n2)입니다.
그러나 정확히 o (log n)는 무엇입니까?예를 들어, 완전한 이진 트리의 높이가 O (log n)라고 말하는 것은 무엇을 의미합니까?
저는 (아마도 세부 사항이 아닐 수도 있습니다) 어떤 로그가 무엇인지, log10 100 = 2 그러나 로그 시간과 함수를 식별하는 방법을 이해할 수는 없습니다.
답변
로그 시간으로 함수를 식별하는 방법을 이해할 수 없습니다.
로그 러닝 타임 기능의 가장 일반적인 속성은 다음과 같습니다.
일부 행동을 수행 할 다음 요소의 선택은 여러 가지 가능성 중 하나입니다. 하나만 선택해야합니다.
또는
조치가 수행되는 요소는 n의 자릿수입니다.
이것은 예를 들어 전화 번호부에서 사람들을 찾는 이유입니다 (log n).전화 번호부의 모든 사람을 확인하여 올바른 것을 찾을 필요가 없습니다.대신 이름이 알파벳 순으로 표시되는 위치를 기반으로보고 - 정복을 나눌 수 있습니다. 모든 섹션에서 결국 누군가의 전화 번호를 찾기 전에 각 섹션의 하위 집합을 탐색하는 데 필요한 모든 섹션에서만 나눌 수 있습니다.
물론, 더 큰 전화 번호부는 여전히 더 긴 시간이 걸릴 것입니다. 그러나 추가 크기의 비례 증가만큼 빨리 자라지 않을 것입니다.
우리는 다른 종류의 작업과 실행 시간을 비교하기 위해 전화 번호부 예제를 확장 할 수 있습니다.우리는 우리의 전화 번호부가 고유 한 이름을 갖지 않을 수있는 고유 한 이름과 사람 ( "흰색 페이지")을 가진 비즈니스가있는 비즈니스 ( "옐로우 페이지")가 있다고 가정합니다.전화 번호는 대부분의 한 사람이나 비즈니스에 할당됩니다.또한 특정 페이지에 뒤집을 수있는 일정한 시간이 걸리지 않는다고 가정합니다.
다음은 우리가 전화 번호부에서 가장 빠른에서 가장 느린 작업에서 수행 할 수있는 작업의 실행 시간입니다.
o (1) (최악의 경우) : 비즈니스 이름이 켜져 있고 비즈니스 이름이 전화 번호를 찾으면 전화 번호를 찾습니다. o (1) (평균 사례) : 사람의 이름이 켜져있는 페이지와 이름을 지정하면 전화 번호를 찾습니다. o (log n) : 사람의 이름을 감안할 때 아직 검색하지 않은 책의 일부를 통해 중간에 무작위 지점을 선택한 다음 그 시점에 있는지 여부를 확인하십시오. 그런 다음 그 사람의 이름이 거짓말하는 책의 일부를 반복하는 과정을 반복하십시오. (이것은 사람의 이름을위한 바이너리 검색입니다.) o (n) : 전화 번호가 포함 된 모든 사람들이 숫자 "5"를 포함합니다. o (n) : 전화 번호를 감안할 때 그 전화 번호로 그 사람이나 사업을 찾으십시오. o (n log n) : 프린터의 사무실에서 믹스 업이 있었고, 우리의 전화 번호부는 모든 페이지가 무작위 순서로 삽입 된 것으로 나타났습니다. 각 페이지의 첫 번째 이름을보고 해당 페이지를 새롭고 빈 전화 번호부에 적절한 장소에두면 주문을 수정하십시오.
아래의 예제에서는 현재 프린터의 사무실에 있습니다.전화 번호부는 각 거주자 또는 비즈니스에 우편으로 발송되기를 기다리고 있으며, 우편으로 보내야하는 곳을 식별하는 각 전화 번호부에 스티커가 있습니다.모든 사람이나 사업은 한 번의 전화 번호부를 얻습니다.
o (n log n) : 우리는 전화 번호부를 개인화하고 싶습니다. 그래서 우리는 지정된 사본에서 각 사람이나 비즈니스의 이름을 찾고 책에 이름을 동그라미켜서 짧은 감사를 씁니다. ...에 o (N2) : 사무실에서 실수가 발생했으며 전화 번호부의 각 항목에는 전화 번호가 끝나면 추가 "0"이 있습니다. 흰색을 가져 와서 각 0을 제거하십시오. o (n · n!) : 우리는 선적 독에 전화 번호부를로드 할 준비가되었습니다. 불행히도, 책을로드 해야하는 로봇은 건초 와이어가갔습니다. 책을 무작위로 트럭에 넣는 것! 더욱 악화되면 모든 책을 트럭에로드 한 다음 올바른 순서가 있는지 확인하고 그렇지 않은 경우가 아니라면이를 언로드하고 시작합니다. (이것은 두려운보고 정렬입니다.) o (nn) : 일을 올바르게로드하도록 로봇을 수정합니다. 다음날, 귀하의 동료 중 한 명은 귀하의 장난을 연주하고 로딩 도크 로봇을 자동 인쇄 시스템으로 전선합니다. 로봇이 원래의 책을로드하기 위해서는 공장 프린터가 모든 전화 번호부를 중복 한 실행을합니다! 다행히도 로봇의 버그 탐지 시스템은 로봇이로드 할 중복 된 책을 만날 때 로봇이 더 많은 사본을 인쇄하지 않지만 인쇄 된 모든 원본 및 중복 된 책을로드해야합니다.
답변
o (log n) 기본적으로 n은 선형으로 일어나서 n은 기하 급수적으로 올라갑니다.따라서 10 개의 요소를 계산하기 위해 1 초가 걸리면 100 개의 요소를 계산하는 데 2 초가 걸리고 1000 개의 요소를 계산하는 데 3 초가 걸립니다.
우리가 나누어 줌 할 때 o (log n) e.g 바이너리 검색의 유형을 정복 할 때입니다.또 다른 예는 배열을 두 부분으로 나누기 위해 배열을 두 부분으로 나눌 때마다 Pivot 요소를 찾기 위해 o (n) 시간을 소요될 때마다 빠르게 정렬됩니다.따라서 o (log n)
답변
개요
다른 사람들은 트리 다이어그램과 같은 좋은 다이어그램 예제를주었습니다.간단한 코드 예제가 보이지 않았습니다.따라서 내 설명 외에도 다른 알고리즘 카테고리의 복잡성을 설명하기 위해 간단한 Print 문을 사용하여 일부 알고리즘을 제공 할 것입니다.
첫째, 당신은 https://en.wikipedia.org/wiki/logarithm에서 얻을 수있는 일반적인 아이디어를 원할 것입니다.자연 과학은 E와 자연 로그를 사용합니다.엔지니어링 제자는 log_10 (로그베이스 10)을 사용하고 컴퓨터 과학자는 컴퓨터가 바이너리 기반이므로 log_2 (로그베이스 2)를 많이 사용합니다.때로는 자연 로그의 약어가 LN ()으로 표시되며 엔지니어는 일반적으로 _10을 꺼지고 log ()을 사용하기 만하면 LG ()로 축약됩니다.유사한 유사한 유사한 로그 유형의 모든 유형이 자라며, 그래서 그들은 동일한 카테고리 (n)를 공유합니다.
아래 코드 예제를 볼 때 O (1), 다음 o (n), o (n ^ 2)를 보는 것이 좋습니다.당신이 그것들과 함께 좋은 후에, 다른 사람들을보십시오.미묘한 변화가 여전히 동일한 분류를 초래할 수있는 방법을 보여주는 방법을 보여주는 정리 예제뿐만 아니라 청정 예제를 포함했습니다.
O (1), o (n), o (logn) 등을 수업이나 범주로 생각할 수 있습니다.일부 카테고리는 다른 것보다 더 많은 시간을 할애 할 것입니다.이러한 범주는 알고리즘 성능을 주문할 수있는 방법을 제공합니다.일부는 입력 N이 증가함에 따라 더 빨리 성장합니다.다음 표는 수치 적으로 상기 성장을 보여줍니다.아래 표에서는 log_2의 천장으로 로그 (n)을 생각합니다.
다양한 빅 O 카테고리의 간단한 코드 예제 :
o (1) - 일정한 시간 예 :
알고리즘 1 :
알고리즘 1은 Hello를 한 번 인쇄하며 N은 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의 현재 값을 2로 배수하므로 1에서 2 ~ 4에서 8 ~ 8에서 16 ~ 32 ...
for(int i = 1; i <= n; i = i * 2)
print "hello";
알고리즘 4 - 이것은 "log_3"처럼 작동합니다.
알고리즘 4는 log_3을 보여줍니다.고지 나는 1에서 3에서 3에서 9까지의 ...
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 Times를 인쇄합니다.
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(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 cubed 예제 :
알고리즘 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";
요약
위의 내용은 몇 가지 똑바로 전달 예를 제공하고, 분석을 정말로 변경하지 않는 미묘한 변화를 어떻게 도입 할 수 있는지 보여주기위한 변형을 제공합니다.바라건대 당신에게 충분한 통찰력을주는 것입니다.
답변
많은 좋은 답변이 이미이 질문에 게시되었지만, 우리가 정말로 중요한 것 - 즉, 일러스트 답변을 누락했다고 믿습니다.
완전한 이진 트리의 높이가 O (log n)라고 말하는 것은 무엇을 의미합니까?
다음 그림 그리기는 이진 트리를 묘사합니다.각 레벨이있는 방법 위의 레벨에 비해 노드 수를 두 배로 포함하는지 확인하십시오.
바이너리 검색은 복잡성 O (log n)의 예입니다.그림 1의 트리의 하단 레벨의 노드가 일부 정렬 된 컬렉션의 항목을 나타냅니다.바이너리 검색은 분할 및 정복 된 알고리즘이며, 도면은이 16 개 항목 데이터 세트에서 검색하는 레코드를 찾기 위해 4 개의 비교를 통해 4 개의 비교를 보여줍니다.
32 개의 요소가있는 데이터 집합 대신에 우리가 가정했다.우리가 데이터의 양을 곱하면 나무가 하나의 레벨이 더 깊이 자란 것처럼 우리가 검색하는 것을 찾는 것처럼 우리가 검색하는 것을 찾을 수 있으므로 위의 그림을 찾으려면 위의 그림을 계속하십시오.결과적으로, 알고리즘의 복잡성은 대수 순서로 설명 될 수 있습니다.
플로팅 로그 (n)는 일반 종이에 곡선의 상승이 증가함에 따라 곡선의 상승이 증가하는 그래프가됩니다.
답변
로그
OK 실제로 로그가 무엇인지를 완전히 이해하겠습니다.
우리가 로프가 있고 우리는 그것을 말에 묶었습니다.로프가 말에 직접 묶여있는 경우, 말이 말을 끌어 들일 필요가있는 힘 (말, 사람에게서)은 직접 1입니다.
이제 로프가 기둥을 둥글게 묶는 것을 상상해보십시오.멀리 나가는 말은 이제 여러 번 더 어려워 야합니다.횟수는 로프의 거칠기와 극의 크기에 따라 달라 지지만, 강도가 10만큼 곱할 것이라고 가정 해 봅시다 (로프가 완전한 회전을 할 때).
이제 로프가 한 번 루프되면 말은 10 배 더 열심히 당겨야합니다.인간이 말을 정말로 어렵게 만들기로 결정하면, 그는 로프를 다시 한 번 둥글게 묶을 수 있고, 그것이 힘의 힘을 10 회까지 증가시킬 수 있습니다.세 번째 루프는 다시 10 회 이상 강도를 증가시킵니다.
우리는 각 루프에 대해 10이 늘립니다. 숫자를 얻는 데 필요한 턴 수는 I.E.E의 대수를 얻는 데 필요한 턴 수를 1,000 배에 대해 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을 사용하지만 다행히도 로그의 기초는 우리가 큰 o 표기법에 대해 이야기 할 때 중요하지 않습니다.
이제 당신이 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
그래프를 사용하여 2 진수를 사용하여 1-100 사이의 숫자를 추측하면 대부분의 7 가지 시도에서 우리를 데려 갈 것입니다.우리가 128 개의 숫자가 있으면 7 개의 Athemps의 숫자를 추측 할 수 있지만 129 개의 숫자는 대부분의 8 번 시도 (로그에 관계없이 128 개의 가치 범위에 대한 7 가지 추측이 필요할 것입니다, 1024 가치 범위에 대한 10 가지 추측이 필요합니다).7 7은 128, 10의 대수는 1024 (기본 2)의 대수입니다.
나는 대부분의 '굵게 표시되었다.BIG-O 표기법은 항상 악화 된 경우를 나타냅니다.운이 좋으면 한 번 시도한 숫자를 추측 할 수 있으므로 가장 좋은 경우는 O (1)이지만 다른 이야기입니다.
우리는 모든 추측에 대해 데이터 세트가 줄어들고 있음을 알 수 있습니다.알고리즘에 로그가있는 경우 식별하는 것의 좋은 규칙은 각 반복 후에 데이터 세트가 특정 순서로 축소되는지 확인하려면
o (n log n)는 어떻습니까?
결국 선생심 시간 (n log (n)) 알고리즘을 가로 질러 올 것입니다.위의 엄지 손가락의 규칙이 다시 적용되지만 이번에는 로그 함수가 n 번을 실행해야합니다.메러 포트와 같은 알고리즘에서 발생하는 목록 n 번의 크기를 줄입니다.
알고리즘 시간이 n log n인지 쉽게 식별 할 수 있습니다.목록을 통해 반복하는 외부 루프를 찾습니다 (o (n)).그런 다음 내부 루프가 있는지 확인하십시오.내부 루프가 각 반복에 설정된 데이터 세트를 절단 / 줄이면 해당 루프가 (O (로그 N))이므로 전체 알고리즘이 = o (n log n)입니다.
면책 조항 : 로프 - 로그 예제는 W.Wyyer의 우수한 수학자의 기쁨 책에서 가져 왔습니다.
답변
필요한 기능이있는 경우 :
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.
그런 다음 log2 (n) 시간이 걸립니다.느슨하게 말하면서, 느슨하게 말하면서, 관계가 큰 n에만 해당되어야하고, 일정한 요인과 더 작은 용어는 무시할 수 있음을 의미합니다.
출처:https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly
최근댓글