240418 Java

복잡도 : 알고리즘의 성능을 나타내는 지표

시간복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

• 오메가 표기법(Big-Ω Notation) : 최상의 경우(best case)
• 세타 표기법(Big-Θ Notation) : 평균의 경우(average case)
• 빅오 표기법(Big-O Natation) : 최악의 경우(worst case)

입력 크기(n)에 따른 단위 연산의 수행 횟수 변화를 함수로 나타낸 것

 

T(n) = 3n^2 + 2n + 8;

n : 입력 횟수 증가,

3n^2 + 2n + 8 : 연산 단위 수행 횟수 증가

 

점진적 표기법 : Asymptotic Notation

시간복잡도 함수를 대표적인 복잡도 함수 집합의 원소로 표현하는 방법

1. 알고리즘의 기본연산을 찾음
2. 기본 연산이 실행되는 횟수를 입력 크기에 대한 함수로 나타냄
3. 입력 크기에 대한 함수를 단순화하고 단순화된 함수에서 가장 높은 차수의 항만을 남기고, 계수를 제외
4. 최종적으로 남은 항이 시간 복잡도임

입력 크기(n)에 따른 단위 연산의 수행 횟수 변화를 함수로 나타낸 것

---

가장 높은 차수

T(n) ∈ O(n);

 

public static void func1(int n){
	for(int i = 1; i <=n ; i++){
    	System.out.println("Complexity");
    }
}
func1(10);

 

public static void func2(int n){
	for(int i = 1; i <= n; i++){
    	System.out.println("complexity : n");
    }
    
    for(int i = 1; i <=2*n ; i++){
		System.out.println("complexity : 2 * n");
    }
	
    for(int i = 1; i <= 3*n ; i++){
		System.out.println("complexity : 3 * n");
    }
}
func2(10);

 

T(n) = n + 2n + 3n = 6n -> n -> O(n)

---

가장 높은 차수

T(n) ∈ O(n^2);

public static void func3(int n){
	for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= n; j++{
        	System.out.println("complexity");
    	}
    }
}    
func3(10);

 

T(n) = n * n -> n^2 -> O(n^2)

---

입력 크기에 따른 실행 횟수가 다양한 경우

가장 높은 차수

T(n) ∈ O(log₂n);

public static void func4(int n){
	for(int i = 1; i <= n; i *=2){
    	System.out.println(i)
	}
}

func4(10);

 

T(n) = log₂n -> O(log ₂n)

---

---

---

---

---