알고리즘의 최악의 경우 시간 복잡도

StackOverflow https://stackoverflow.com/questions/331295

문제

최악의 시간 복잡성 t (n) :- 나는 알고리즘에 대한이 책을 읽고 있으며, 예를 들어 t (n)를 얻는 방법 ....선택 정렬 알고리즘처럼

내가 SelectionSort(A[0..n-1]) 을 다루는 것처럼

//sorts a given array by selection sort
//input: An array A[0..n - 1] of orderable elements.
//output: Array A[0..n-1] sorted in ascending order

의사코드를 작성해 보겠습니다

for i <----0 to n-2 do
  min<--i
for j<--i+1 to n-1 do
   ifA[j]<A[min] min <--j
swap A[i] and A[min]

--------C#으로도 작성하겠습니다---------------

private int[] a = new int[100];

// number of elements in array
private int x;

// Selection Sort Algorithm
public void sortArray()
{
  int i, j;
  int min, temp;

  for( i = 0; i < x-1; i++ )
  {
    min = i;

    for( j = i+1; j < x; j++ )
    {
      if( a[j] < a[min] )
      {
        min = j;
      }
    }

    temp = a[i];
    a[i] = a[min];
    a[min] = temp;
  }
}

==================

이제 t(n) 또는 알려진 최악의 경우 시간 복잡도를 얻는 방법

도움이 되었습니까?

해결책

@사라 존스 당신이 참조한 슬라이드 세트와 그 안의 알고리즘

for 루프의 각 기본/원자적 작업에 대해 복잡성이 측정됩니다.

for(j=0 ; j<n ; j++)
{
    //...    
}

슬라이드에서는 다음과 같은 이유로 이 루프를 2n+2로 평가합니다.

  • j=0(+1 op)의 초기 세트
  • j < n 비교(n ops)
  • j++의 증가(n ops)
  • j < n인지 확인하는 최종 조건(+1 op)

    • 둘째, for 루프 내에서의 비교 

    if(STudID == A[j])      
    return true;

    이는 n ops로 평가됩니다.따라서 +1 op, n ops, n ops, +1 op, n ops = 3n+2 복잡성을 더하면 결과가 됩니다.따라서 T(n) = 3n+2

    T(n)은 O(n)과 동일하지 않다는 점을 인식하세요.

    다른 팁

    그것은 O (n^2)입니다.

    그 이유는 루프를 위해 다른 루프에 둥지를 틀고 있기 때문입니다. 루프의 내부에 대한 실행 시간, O (n)은 루프 용 외부 반복에 대해 발생하며, 이는 다시 O (n)입니다. 이들 각각의 개별적으로 O (n) 인 이유는 입력 크기가 주어지면 선형 시간이 걸리기 때문입니다. 입력이 클수록 선형 스케일에서 더 오래 걸립니다. n.

    이 경우 사소한 수학을 해결하려면 외부 루프의 복잡성에 의해 내부 루프의 복잡성 만 다중. n * n = n^2. 외부 루프의 각 N에 대해 다시 내부를 위해 N을 수행해야합니다. 명확히하기 위해 : 각 n에 대한 n 번.

    o (n * n).

    o (n^2)

    그건 그렇고, 당신은 복잡성 (big-o로 표시)과 t 함수를 혼합해서는 안됩니다. t 함수는 주어진 입력에 대해 알고리즘이 수행 해야하는 단계 수입니다.

    따라서 t (n)의 값은 실제 단계 수이며 O (무언가)는 복잡성을 나타냅니다. 표기법의 기존 남용에 의해, t (n) = o (f (n))은 함수 t (n)이 다른 함수 f (n)과 최대 동일한 복잡성이라는 것을 의미하며, 이는 일반적으로 가장 단순한 기능이 될 것입니다. 복잡성 클래스의.

    이것은 큰 그림에 집중할 수 있기 때문에 유용합니다. 이제 "장기적으로"수행하는 방식을 살펴보면 매우 다른 T (N) 기능을 가질 수있는 두 가지 알고리즘을 쉽게 비교할 수 있습니다.

    또 다른 박사 과정 플래시백.

    첫째, t 함수는 단순히 시간의 양입니다 (일반적으로 일부 숫자에서는 단계, 아래의 더 이상) 알고리즘은 작업을 수행하는 데 걸립니다. "단계"가 무엇인지, 사용에 의해 다소 정의된다. 예를 들어, 정렬 알고리즘의 비교 수를 계산하는 것이 기존의 것이지만 검색 알고리즘에서 검색된 요소 수를 계산하는 것이 기존입니다.

    알고리즘의 최악의 시간에 대해 이야기 할 때, 우리는 일반적으로 "big-o 표기법"으로 그것을 표현합니다. 예를 들어, 거품 정렬이 O (n²) 시간이 걸린다고 들었습니다. 우리가 큰 O 표기법을 사용할 때, 우리가 실제로 말하는 것은 일부 기능 (이 경우 T)의 성장이 다른 기능 시간의 성장보다 빠르지 않다는 것입니다. 그건

    t (n) = O (n²)

    어떤 의미 N, 아무리 큰지, 상수가 있습니다 케이 어느 쪽이든 t (n) ≤ kn². 여기서 혼란의 요점은 우리가 과부하 된 방식으로 "="로그인을 사용하고 있다는 것입니다. 두 사람이 동일한 수치 적 의미에서 t (n) ~이다 kn²에 의해 경계.

    확장 된 질문의 예에서, For 루프와 테스트에서 비교 수를 계산하는 것처럼 보입니다. 그것은 그들이 대답하는 맥락과 질문을 볼 수있게하는 데 도움이 될 것입니다. 어쨌든 우리가 Big-O 표기법을 좋아하는 이유를 보여줍니다. w (n) 여기에 있습니다 에). (증거 : 상수 K, 즉 5가 존재합니다. w (n) ≤ K (3n) +2. 그것은 정의에 따른다 에).)

    이것에 대해 자세히 알아 보려면 좋은 알고리즘 텍스트를 참조하십시오. 알고리즘 소개, Cormen의 et al.

    HAH 테이블에서 학생 정보를 검색, 삽입 및 제거하려면 의사 코드를 작성하십시오. 최고와 최악의 경우 복잡성을 계산하십시오

    3N + 2는 루프에 관한 한 정답입니다. 루프의 각 단계에서 3 개의 원자 연산이 수행됩니다. J ++는 실제로 하나가 아닌 두 가지 작업입니다. 그리고 j

    라이센스 : CC-BY-SA ~와 함께 속성
    제휴하지 않습니다 StackOverflow
    scroll top