상수, N 시간 복잡도

상수

    public int sum(int a, int b){  
        int val = 0;  
        val = a+b;  

        return val;  
    }  

    public static void main(String\[\] args){  
        int a = 10;  
        int b = 5;  

        sum(10, 5);  
    }  

val = a+b;

a+b 더하기를 합니다.
val 변수에 a+b 값을 할당합니다.

프로그램이 한번 실행되고 종료됩니다.
입력 값의 크기에 의존하지 않는 프로그램은 상수 시간만큼 소요됩니다.

N

    public int sum(int val){  
        int added = 0;  

        for(int i = 0; i < val; i++){  
            added += 50;  
        }  

        return added;
    }  

    public static void main (String[] args){  
         int a = 10;  
        int b = 5;  

        sum(3);  
    }  

sum(val) 시간 복잡도 : 4 + 5n

수행 : int added = 0; 초기화

시간 복잡도 = 1
1

수행 : int i = 0; 초기화

시간 복잡도 = 1 + 1
2

수행 : i < val; 반복문 수행, 종료

시간 복잡도 = 1 + 1 + n + 1
3 + n
n : i < val 입력된 val 크기에 의존하여 n번 반복문 실행
1 : i < val 조건이 충족되지 않는다면 false 반환

수행 : added += 50; 수행, 할당

시간 복잡도 = 1 + 1 + n + 1 + 2n
3 + 3n
2n : 0 + 50 수행, 수행 결과를 added 변수에 할당

수행 : i++; 수행, 할당

시간 복잡도 = 1 + 1 + n + 1 + 2n +2n
3 + 5n
2n : 0 + 1 수행, 수행 결과를 i 변수에 할당

수행 : return added; 반환

시간 복잡도 = 1 + 1 + n + 1 + 2n + 2n + 1
4 + 5n
1 : added 변수 반환

정리 목적

프로그램이 몇 번 실행되는지 확인하기 위한 목적으로 작성하였습니다.