누구든지 Java에서 O 표기의 기본 예제를 제공 할 수 있습니까?

Question

o 표기법의 한계를 찾으려고 노력하고 있는데, 버전 1이 버전 2와 동일한 o 표기 인 작업에 대한 enahncement를 보여주는 간단한 예제가 있는지 궁금 해서요. 그러나 버전 2는 향상 후 더 효율적으로 작동합니다.

감사

다음 코드

Answer 1

, 내부 루프가 빠른 기능 잎에서 깰 // do something 후에 라인의 첨가, 여전히 하나 인 O (N^2).

for (int i = 0; i < n; i++) { 
    for (int j = 0; i < n; j++) { 
     if (i == j) { 
      // do something 
     } 
    } 
} 

Answer 2

nLog (N)에서이 병합 - 분류 코드 일 :

/** 
* Mergesort algorithm. 
* @param a an array of Comparable items. 
*/ 
public static void mergeSort(Comparable [ ] a) { 
    Comparable [ ] tmpArray = new Comparable[ a.length ]; 
    mergeSort(a, tmpArray, 0, a.length - 1); 
} 

/** 
* Internal method that makes recursive calls. 
* @param a an array of Comparable items. 
* @param tmpArray an array to place the merged result. 
* @param left the left-most index of the subarray. 
* @param right the right-most index of the subarray. 
*/ 
private static void mergeSort(Comparable [ ] a, Comparable [ ] tmpArray, 
     int left, int right) { 
    if(left < right) { 
     int center = (left + right)/2; 
     mergeSort(a, tmpArray, left, center); 
     mergeSort(a, tmpArray, center + 1, right); 
     merge(a, tmpArray, left, center + 1, right); 
    } 
} 

/** 
* Internal method that merges two sorted halves of a subarray. 
* @param a an array of Comparable items. 
* @param tmpArray an array to place the merged result. 
* @param leftPos the left-most index of the subarray. 
* @param rightPos the index of the start of the second half. 
* @param rightEnd the right-most index of the subarray. 
*/ 
private static void merge(Comparable [ ] a, Comparable [ ] tmpArray, 
     int leftPos, int rightPos, int rightEnd) { 
    int leftEnd = rightPos - 1; 
    int tmpPos = leftPos; 
    int numElements = rightEnd - leftPos + 1; 

    // Main loop 
    while(leftPos <= leftEnd && rightPos <= rightEnd) 
     if(a[ leftPos ].compareTo(a[ rightPos ]) <= 0) 
      tmpArray[ tmpPos++ ] = a[ leftPos++ ]; 
     else 
      tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 

    while(leftPos <= leftEnd) // Copy rest of first half 
     tmpArray[ tmpPos++ ] = a[ leftPos++ ]; 

    while(rightPos <= rightEnd) // Copy rest of right half 
     tmpArray[ tmpPos++ ] = a[ rightPos++ ]; 

    // Copy tmpArray back 
    for(int i = 0; i < numElements; i++, rightEnd--) 
     a[ rightEnd ] = tmpArray[ rightEnd ]; 
} 

Answer 3

O 표기법 기능의 제한 동작을 설명하는 알고리즘을위한 최악. 일반적으로 동일한 작업에 대해 서로 다른 알고리즘을 비교하는 것으로 충분합니다 (예 : 해당 함수로 알고리즘 정렬).

거의 모든 알고리즘 (O (1) 알고리즘 제외)에 대해서는 알고리즘을 더 짧은 시간 (또는 적은 메모리 사용량으로) 종료하는 입력 데이터가 항상 있습니다. 그 알고리즘에 대해서.

private int counter(int n) { 
    int counter; 
    for (int i = 0; i < 2; i++) { 
    counter = 0; 
    for (int i = 0; i < n; i++) { 
     counter++; 
    } 
    } 
    return counter; 
} 

성장은 선형, 그래서이 카운터의 O 표기법은 O (N) (I는 단계에 있지 메모리를 찾고 있어요)입니다 :

우리가 계산 알고리즘 그렇게해야하는 경우를 가정 해 보겠습니다. 이봐 요, 우린 두 번 세고, 대신 O (2n)라고 써주세요. 참된. O (2n + c)를 써서 로컬 변수를 만들고 초기화하는 데 몇 가지 추가 단계 (시간)가 필요하다는 것을 나타낼 수도 있습니다.

private int counter(int n) { 
    int counter =0; 
    for (int i = 0; i < n; i++) { 
    counter++; 
    } 
    return counter; 
} 

모두가 O (N)으로 표현 된 선형 증가를 나타내는 :

여기 여전히 상당히 빠른 선형 (O (N))이지만 종료 개선 구현된다. 예를 들어 이러한 구현을 해당 카운터의 O (n^2) 또는 O (1) 구현과 비교하는 것만으로도 충분할 수 있습니다. 그러나 '선형'버전 A와 B를 비교하기 위해서는보다 정확하고 첫 번째를 O (2n), 두 번째를 O (n)으로 식별해야합니다. 이제 O 표기법 값의 비교는 예상 결과를 제공합니다. 구현 B는 '더 우수'합니다.

Answer 4

질문의 일부를 뒤집을 수 없습니까? 따라서 원활하게 실행되는 버전을 사용하면 원본 코드의 큰 부분을 변경하지 않는 방식으로 비효율적으로 만들 수 있습니다. 예를 들어, 어떤 작업을 수행하는 동안 프로그램이 10 초 동안 잠자기 상태가되도록 라인을 추가하는 것은 일정 시간 변경으로 big-O를 계산할 때 제거됩니다. 이 경우 추가 코드가있는 버전은 버전 1이고 다른 버전은 더 효율적이지만 중요하지 않은 버전 인 버전 2입니다.

big-O는 낮은 차수의 용어와 상수 승수를 무시하기 때문에 좀 더 추상적 인 의미로 대답을 원하면 방법의 전체적인 큰 -O를 변경하지 않고 더 효율적으로 만들 수 있습니다. 죄송합니다. Java 코드가 없지만이 대답은 언어에 구애받지 않습니다.