시간 복잡도 T(n)을 어떻게 찾고 이것이 긴밀하게 묶여 있음(Big Theta)을 표시합니까?

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

문제

최악의 경우에 시간 복잡도를 부여하는 방법을 알아내려고 노력 중입니다.내 분석이 확실하지 않습니다.나는 중첩을 읽었습니다 for 루프 빅 O는 n^2;이게 맞나요? for 루프를 사용하여 while 내부 루프?

// A is an array of real numbers.
// The size of A is n. i,j are of type int, key is
// of type real. 
Procedure IS(A)    
for j = 2 to length[A]     
{                
   key = A[ j ]               
   i = j-1   
   while i>0 and A[i]>key    
   {       
      A[i+1] = A[i]                         
      i=i-1                    
   }                
   A[i+1] = key      
}

지금까지 나는 : 

j=2 (+1 op)  

i>0 (+n ops)   
A[i] > key (+n ops)

so T(n) = 2n+1?

하지만 꼭 안으로 들어가야 할지 잘 모르겠습니다. while 그리고 for 최악의 경우 시간 복잡도를 분석하는 루프...

이제 나는 그것이 단단히 묶여 있다는 것을 증명해야 합니다. 그것이 Big Theta입니다.

나는 그 중첩된 내용을 읽었습니다. for 루프에는 Big O가 있습니다. n^2.Big Theta도 마찬가지인가요?그렇지 않다면 어떻게 Big Theta를 찾을 수 있을까요?!

**C1= C sub 1, C2= C sub 2, no= n 모두 양의 실수 요소입니다.

찾으려면 T(n) 가치관을 살펴보니 j while 루프가 몇 번 실행되었는지 살펴보았습니다.

values of J:   2, 3, 4, ... n  
Loop executes: 1, 2, 3, ... n

분석:
while 루프 실행을 요약하고 그것이 다음과 같다는 것을 인식합니다. (n(n+1))/2이것을 내 것으로 지정하겠습니다. T(n) 그리고 그것이 단단히 묶여 있음을 증명하십시오. n^2.그건 n(n+1)/2= θ(n^2)

스크래치 작업:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)for all n ≥ no

To make 0 ≤ C1(n) true, C1, no, can be any positive reals   
To make C1(n^2) ≤ (n(n+1))/2, C1 must be ≤ 1  
To make (n(n+1))/2 ≤ C2(n^2), C2 must be ≥ 1

PF:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no
Let C1= 1/2, C2= 1 and no = 1.

  1. 0 ≤ c1 (n^2)이 true c1 (n^2) = n^2/2임을 보여줍니다.
    n^2/2≥ no^2/2
    ⇒아니요^2/2≥ 0
    1/2 > 0
    따라서 C1(n^2) ≥ 0이 참임이 입증되었습니다!

  2. C1 (n^2) ≤ (n (n+1))/2가 true c1 (n^2) ≤ (n (n+1))/2임을 보여줍니다.
    n^2/2 ≤ (n (n+1))/2 n^2 ≤ n (n+1)
    n^2 ≤ n^2+n
    0 ≤ n

    우리가 아는 것은 n ≥ no = 1이기 때문에 사실입니다.
    따라서 C1(n^2) ≤ (n(n+1))/2가 참임이 입증되었습니다!

  3. (n (n+1))/2 ≤ c2 (n^2)가 true (n (n+1))/2 ≤ c2 (n^2)임을 보여줍니다.
    (n+1)/2 ≤ C2(n)
    n+1 ≤ 2 C2(n)
    n+1 ≤ 2(n)
    1 ≤ 2n-n
    1 ≤ n(2-1) = n
    1≤n
    또한 n ≥ no = 1이므로 이것이 사실임을 알 수 있습니다.

    따라서 1, 2, 3에 의해 θ(n^2 )= (n(n+1))/2는 다음과 같습니다.
    모든 n ≥ no에 대해 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)

무슨 일인지 말해보세요 여러분...저는 이 자료를 이해하려고 노력하고 있으며 여러분의 의견을 듣고 싶습니다!

도움이 되었습니까?

해결책

당신은 그것을 구현하는 것 같습니다 삽입 정렬 알고리즘, Wikipedia가 주장하는 것은 O (n2).

일반적으로 BIG-O를 처리 할 때 상수 C가 아닌 변수 N을 기준으로 구성 요소를 분류합니다. 귀하의 경우, 당신이해야 할 일은 루프를 보는 것입니다.

두 루프가 (더 나쁜 경우) :

for j=2 to length[A]
    i=j-1
    while i > 0
        /*action*/
        i=i-1

외부 루프는 O (n)이므로 요소 수와 직접 관련되어 있기 때문입니다.

내부 루프가 외부 루프의 진행 상황에 어떻게 의존하는지 확인하십시오. 즉, 내부 및 외부 루프가 (나오지 않은 문제를 무시하는) 다음과 관련이 있음을 의미합니다.

 j's     inner
value    loops
-----    -----
  2        1
  3        2
  4        3
  N       N-1
-----    -----
total    (N-1)*N/2

그래서 총 횟수 /*action*/ is is (n2 -N)/2, O (n)2).

다른 팁

중첩 루프의 수를 보는 것이 솔루션을 얻는 가장 좋은 방법은 아닙니다. 코드에서 수행중인 "작업"을 무거운 부하 N으로 보는 것이 좋습니다. 예를 들어,, 예를 들어,

for(int i = 0; i < a.size(); i++)
{
  for(int j = 0; j < a.size(); j++)
  {
    // Do stuff
    i++;
  }
}

O (n)입니다.

함수 F는 G의 큰 OH와 G의 Big-Omega에있는 경우 g의 큰 g에 있습니다. 최악의 경우는 데이터 A가 단조롭게도 기능을 감소시킬 때 발생합니다. 그런 다음 외부 루프의 모든 반복에 대해 while 루프가 실행됩니다. 각 명령문이 1의 시간 값을 기여한 경우 총 시간은 5*(1 + 2 + ... + n -2) = 5*(n -2)*(n -1) / 2입니다. 데이터에 대한 2 차 의존성. 그러나 데이터 A가 단조로 증가하는 시퀀스 인 경우, 조건 A [I]> 키는 항상 실패합니다. 따라서 외부 루프는 일정한 시간에 n -3 번 실행됩니다. F의 가장 좋은 경우는 데이터에 선형 의존성을 갖습니다. 평균적인 경우, 우리는 다음 숫자를 A에서 가져 와서 이전에 발생한 분류에서 그 자리를 찾습니다. 평균적 으로이 숫자는이 범위의 중간에있을 것이며, 이는 내부가 최악의 경우보다 자주 절반으로 실행되므로 데이터에 2 차 의존성을 제공합니다.

Big O(기본적으로) 작업을 완료하기 위해 루프의 요소를 몇 번이나 검토할지에 대한 것입니다.

예를 들어 O(n) 알고리즘은 모든 요소를 ​​한 번만 반복합니다.O(1) 알고리즘은 모든 요소를 ​​전혀 반복할 필요가 없으며 인덱스가 있기 때문에 배열에서 찾아야 할 위치를 정확히 알 수 있습니다.이에 대한 예는 배열 또는 해시 테이블입니다.

루프 내부의 루프가 O(n^2)인 이유는 루프의 모든 요소가 자체적으로 ^2번 반복되어야 하기 때문입니다.루프 유형을 변경하는 것은 기본적으로 약 #회 반복이므로 이와 관련이 없습니다.

필요한 반복 횟수를 줄일 수 있는 알고리즘에 대한 접근 방식이 있습니다.그 예로는 "분할 및 정복" 같은 알고리즘 퀵소트, 내가 올바르게 기억한다면 이는 O(nlog(n))입니다.

달성하려는 목표를 보다 구체적으로 알지 못한 채 예시에 대한 더 나은 대안을 찾는 것은 어렵습니다.

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