Big Oh for (n log n)

Question

현재 Big Oh에 대한 기본 알고리즘을 연구 중입니다. Big Oh를 사용하는 Java의 코드 (n log n)가 어떤 것인지 알려줄 수 있는지 궁금 해서요.

나는 초보자이므로 글을 작성하기 전에 코드를 상상할 수 있습니다. 그래서, 이론적으로 (적어도), 그것은 우리가 n 배의 무언가를 가지고있는 루프를위한 하나를 포함해야합니다. 그런 다음 로그 n에 대해 while 루프를 사용할 수 있습니다. 그러면 루프가 n 번 실행되고 while 루프는 로그베이스가 2 번 실행됩니다. 적어도 그것은 내가 머리 속에서 상상하고있는 것이지만, 코드를 보는 것은 일을 정리할 것입니다.

Answer 1

매우 인기있는 O (n log n) 알고리즘은 병합 정렬입니다. 알고리즘 및 의사 코드의 예를 들어 http://en.wikipedia.org/wiki/Merge_sort. 알고리즘의 로그 부분은 문제를 작은 하위 문제로 분해하여 재귀 트리의 높이가 로그 n 인 경우에 달성됩니다.

대다수 정렬 알고리즘은 실행 시간이 O (n log n)입니다. 더 많은 예제는 http://en.wikipedia.org/wiki/Sorting_algorithm을 참조하십시오. 로그 (n)의 시간이 소요됩니다 몇 가지 작업을 실행 n 번 -

Answer 2

http://en.wikipedia.org/wiki/Heapsort

간단한 예는 설명처럼입니다. 균형 이진 트리에는 log (n) 높이가 있으므로 일부 트리 알고리즘은 이러한 복잡성을 갖습니다.

Answer 3

int n = 100 
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n) 
{ 
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times 
    { 

    } 
} 

설명 : 외부 for 루프는 명확해야합니다. 실행 된 n 번. 이제 내부 루프에. 내부 루프에서는 n을 입력하고 항상 2으로 나눕니다. 그래서 당신 자신에게 물어보십시오 : 얼마나 많은 시간을 n에 의해 2으로 나눌 수 있습니까?

이것이 O (log n) 인 것으로 나타났습니다. (실제로 로그의베이스는 2이지만 big-oh 표기법에서는 우리가 관심이없는 로그에 몇 가지 요소 만 추가하기 때문에베이스를 남겨 둡니다).

그래서 루프 n 번을 실행 중이며 그 루프 내에서 다른 루프 log(n) 번을 실행 중이므로 O(n) * O(log n) = O(n log n)이됩니다.

Answer 4

O(.) 복잡도가있는 알고리즘은 log n과 같이 일반적으로 몇 가지 형태의 나누기와 정복을 필요로합니다.

예를 들어 MergeSort에서 목록은 반으로 나누어지고 각 부분은 개별적으로 병합 정렬 된 다음 두 개의 반쪽이 함께 병합됩니다. 각 목록은 이고 반자본은입니다.

작업량이 절반으로 줄어들거나 고정 된 크기로 축소 될 때마다 구성 요소가 보통 O(.)이됩니다.

코드 측면에서 MergeSort의 알고리즘을 살펴보십시오. 일반적인 구현의 중요한 특징은 재귀 적이라는 점입니다 (참고로 TopDownSplitMerge은 위키피디아의 코드에서 두 번 부릅니다).

좋은 표준 정렬 알고리즘은 모두 O(n log n) 시간 복잡도가 있으며 최악의 경우 더 잘 수행 할 수 없습니다 (Comparison Sort 참조).

자바 코드에서 어떻게 보이는지 보려면 search! Here's one example.