계산 나는 다음과 같은 C에 대한 큰-O 실행 시간을 계산 ++ 기능을 몇 가지 지침 절실히 필요 해요 런타임

Question

큰-O : 이것은 나에게 새로운 개념은 여전히 ​​

Fraction Polynomial::solve(const Fraction& x) const{ 
    Fraction rc; 
    auto it=poly_.begin(); 
    while(it!=poly_.end()){ 
     Term t=*it; 
     //find x^exp 
     Fraction curr(1,1); 
     for(int i=0;i<t.exponent_;i++){ 
      curr=curr*x; 
     } 
     rc+=t.coefficient_*curr; 
     it++; 
    } 
    return rc; 
} 

, 그래서 나는 데 그것을 올바르게하는 것에 관한 약간의 문제. 나는 한 번 (자동 it = poly_.begin 및 끝에 rc 반환) 적어도 두 번 작업이 있다고 가정하지만 while 루프 사용하여 작업 수를 계산하는 방법을 잘 모르겠습니다. 내 교수에 따르면 올바른 런타임은 O (n)이 아닙니다. 누구라도 지침을 제시 할 수 있다면 크게 환영 할 것입니다. 이 질문에 대답하는 방법을 이해하고 싶지만 온라인에서이 기능을 찾을 수 없습니다. 그래서 여기 있습니다. 고맙습니다.

Answer 1

난 당신이 특정 다항식을 평가하려는 가정에 (우리가 A_n*X^n + ... + A_0를 가정 해 봅시다) 주어진 점 (분수로 주어지기 때문에 합리적인 값).

첫 번째 while 루프는 다항식의 모든 개별 구성 요소를 반복합니다. n 차 다항식의 경우, 이는 n + 1 반복을 산출 할 것이므로 외부 루프만으로도 O (n) 시간이 걸립니다. 그러나 다항식의 모든 항 (우리가 순위 i라고합시다)에 대해 X^i의 값을 계산해야하며, 이는 내부 for 루프가하는 것입니다. 선형 방법을 사용하여 X^i을 계산하여 선형 복잡성을 산출합니다. O (i).

두 개의 중첩 루프가 있으므로 전반적인 복잡도는 루프의 최악의 시간 복잡도를 곱하여 얻습니다. 결과 복잡성은 O (n) * O (n) = O (n^2)에 의해 주어진다. 첫 번째 용어는 while 루프의 복잡성을 나타내며 두 ​​번째 것은 X^i의 컴퓨팅에 대한 최악의 경우의 시간 복잡도를 나타내며, 이는 i == n 일 때 O (n)입니다.

Answer 2

이것이 n 차 다항식이라고 가정합니다 (가장 높은 항은 n의 제곱으로 나옵니다).

외부 while 루프에서 n + 1 항을 반복합니다 (양쪽 모두 0에서 n 포함).

각 용어에 대해 inner for 루프에서 m을 곱하기를 수행하면 m은 현재 용어의 힘입니다. 이것은 n 차 다항식이므로 m은 0에서 n까지입니다. 평균적으로 n/2 번 곱셈을 수행합니다.

전체 복잡도는 O 될 것입니다 ((N + 1) * (N/2)) = O는 (N^2)