Java 최우선 및 최악의 경우의 복잡도

Question

이 Java 프로그램에서 가장 좋고 최악의 경우는 무엇입니까? 최악의 경우는 O (n^2)와 Best case O (n) 또는 O (1)라고 생각합니다. 목록이 이미 정렬 된 경우 O (1)에서 최상의 사례를 간단하게 말할 수 있습니까? 배열이 비어 있다면? 가장 좋은 경우 O (0)을 만들까요? 누구든지 제게 설명해 주시겠습니까?

내 두 센트 여기에 순간적 후 사전

 public class playground { 
     static void printSimpleMedian(int[] arr) { 
    if (arr == null || arr.length == 0) { 
     System.out.println("Array is empty"); 
    } else { 
     boolean sorted = true; 
     for (int i = 0; i < arr.length - 1; i++) { 
      if (arr[i] > arr[i + 1]) { 
       sorted = false; 
      } 
     } 
     if (!sorted) { 
      for (int i = 0; i < arr.length/2; i++) { 
       int max = i; 
       int min = i; 
       for (int j = i; j < arr.length - i; j++) { 
        if (arr[max] < arr[j]) { 
         max = j; 

        } 
     //System.out.print(max); 
       } 

       for (int j = i; j < arr.length - i; j++) { 

        if (arr[min] > arr[j]) { 
         min = j; 
        } 
        //System.out.print(min); 
       } 

       int tmp = arr[i]; 

       arr[i] = arr[min]; 

       arr[min] = tmp; 

       tmp = arr[arr.length - i - 1]; 

       arr[arr.length - i - 1] = arr[max]; 

       arr[max] = tmp; 
      } 
     } 

     // if array length is even upper median is chosen 

     System.out.println(arr[arr.length/2]); 
     } 
    } 



    } 

Answer 1

에 감사하다 : 나는 O (0) 어떤 실제적인 의미가 있다고 생각하지 않는다

• . 이 링크를 살펴 보겠습니다 : Is the time complexity of the empty algorithm O(0)?. 빈 배열의 경우, 일정 시간, O (1)에서 실행되지만, 입력이없는 특수한 경우는이 논리의 라인을 따라 가야한다고 생각하지 않습니다. 우리는 모든 알고리즘의 복잡성이 최선의 경우에 대해 일정하고 전체 O 표기법의 목적을 무력화시키는 것처럼 보이는 것을 나타낼 수 있습니다.

• 최상의 경우 어레이가 정렬 될 때 비교 연산 O (n) 횟수를 수행하고 있습니다.

• 최악의 경우 첫 번째 루프는 O (n), 두 번째 루프는 한 번, 두 개의 별도 내부 루프가 있으므로 O (n * 2n) = O (2n^2)) = O (n^2)이므로 O (n + n^2) = O (n^2)입니다.