다항식

f(X) = a0 + a1x + a2x^2 + ... + an-1 X^n-1

n-1차 다항식 
n개의 계수가 리스트 A에 저장되어있음. 
 
public List A;

 

 

v_n2(A,x)
f(x)를 계산하고 그 값을 리턴하는데, O(n^2) 시간의 계산이 필요한 함수 - 각 항을 O(n) 시간에 계산함.

def v_n2(A, x): //n2함수 
    result = 0.0 //결과 반환 변수
    n = len(A) //인자의 총 갯수
    
    for i in range(n): //for구문 (for i = 0; i < n; i++)랑 같음 
        val = 1.0  //x^0 = A(i)에 대해 X(i) 값을 저장 i=2면 val = x^2
                        //밑에 루프 돌기 전에 계속 초기화됨. 
        for j in range(i): //for구문 (이중for문.)
            val *= x  //x^i 계산 => x를 i번 곱함. 
        
        result += A[i] * val //계수와 항을 곱함
    
    return result

 

 

v_n(A,x)
f(x)를 계산하고 그 값을 리턴하는데, O(n) 시간의 계산히 필요한 함수 - 각 항을 O(1)시간에 계산함

def v_n(A, x): //n 함수 (리스트, x값)
    result = 0.0 //결과 변수 초기화
    n = len(A) //a갯수. (= List A; .... A.count)
    
    for i in range(n - 1, -1, -1): //for( i = (n-1); i > 0, i--) .. n-1부터 역순으로  
        result = result * x + A[i]  //result 업데이트 ... 결과에 x곱하고 현재 인자 A(i) 더함. Result = Result x X + A[i]
    
    return result //결과 반환