📚 시간 복잡도와 Big-O 표기법

시간 복잡도란?

• 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.
• 일반적으로 1초 = 1억 번의 연산을 의미한다.
• 문제에 시간 제한이 2초로 되어 있다면 2억 번의 연산 안에 답이 나와야 한다는 의미이다.
• 시간 복잡도를 따질 때는 데이터의 개수와 제한 시간을 본다. 그리고 이에 알맞은 알고리즘을 사용해야 한다.
• 연산 횟수은 알고리즘 시간복잡도 x 데이터의 크기으로 계산한다.

---

시간 복잡도를 표현하는 방식

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

📚 점근적 표기법은 다음 세가지가 있는데 시간복잡도를 나타내는데 사용된다.

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation) 👈

📚 시간복잡도를 구하는 요령

• 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
• 컬렉션의 절반 이상 을 반복 하는 경우 : O(n/2) -> O(n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O(n+m) -> O(n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O(n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O(n*m) -> O(n²)
• 컬렉션 정렬을 사용하는 경우 : O(n*log(n))

---

Big-0 표기법

java 활용해서 '시간 복잡도' 정리하기!!(개념+코드)

시간복잡도 Big-O(빅오)란?

✅ 요약 정리

오른쪽으로 갈수록 계산 시간은 오래 걸린다!

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

🐨 O(1) - 상수 시간

입력값 n이 주어졌을 때, 연산이 1번만 수행

public class timeComplexity { 
    public static void main(String[] args) { 
        int constant = 1; // 시간 복잡도: O(1) 
    }
}

🐨 O(n) - 직선적 시간

문제를 해결하기 위한 단계의 수와 입력값 n이 1:1의 관계를 가진다. (n이 커지는 만큼 정직하게 1대1로 정비례하는 듯)

public class timeComplexity { 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);        
        int inputNum = sc.nextInt();
        int sum = 0; // 총 합계
        int increment = 1;    // 더해줄 수     

        for(int i=0; i<inputNum; i++){ // inputNum이 커질수록 그에 비례해서 합계가 커짐 
            sum += increment;            
        }
    }
}

🐨 O(n^2) - 2차 시간

문제를 해결하기 위한 단계의 수는 입력값의 제곱이다.

public class timeComplexity { 
    public static void main(String[] args) { 
        int n=9;        
        int gugudan=0;
        
        for(int i=1; i<=n; i++) {            
            for(int j=1; j<=n; j++) {                
                gugudan = i*j;
                System.out.println(i+ "*" + j + "=" + gugudan);
            }
        }
    }
}

🐨 O(C^n) - 지수 시간: 문제를 해결하기 위한 단계의 수는 주어진 상수 C의 n제곱이다.

🐨 O(log n) - 로그 시간 : 입력값 n이 주어졌을 때, 특정한 요건에 따라 필요한 단계가 연산이 줄어 든다. (대표적으로 이진트리 검색)

public int binarySearch(int key, int[] arr, int start, int end) {
	if (start > end) {
		return -1;
	}
	int mid = (start + end) / 2;
	if (arr[mid] == key) {
		return mid;
	} else if (arr[mid] > key) {
		return binarySearch(key, arr, start, mid-1);
	} else {
		return binarySearch(key, arr, mid-1, end);
	}
}

• 위 사진에서 정렬된 숫자 1~9에서 key값이 6인 숫자를 검색하는 것을 보여주고 있다.

• 처음 중간인 5부터 확인하여 비교한다. key값이 더 크므로 왼쪽은 비교할 필요가 없고, 오른쪽만 비교한다.

• 오른쪽에서 중간인 7을 비교한다. key값이 더 작으므로 오른쪽은 비교할 필요가 없고, 왼쪽만 비교한다.

• 남은 공간에서 중간인 6을 비교한다. key값과 동일하므로 종료한다.

• 이런 식으로 데이터를 한 번 찾을 때마다 반틈씩 없어지는 알고리즘을 O(log n) 이라고 한다.

• 이런 방식은 순차 검색 O(n)보다도 훨씬 빠르다.

🐨 O(2^n) - Exponential Time

피보나치(Fibonacci) 수열로 비유할 수 있다

• 매번 함수가 호출될 때마다 2번씩 호출하게 된다.
• 이 호출하는 횟수는 트리의 높이만큼 반복된다. 따라서 O(2^n)의 시간 복잡도를 가지게 된다.
• 즉, 모든 함수의 호출을 일일이 계산해야 한다.
• (이 설명은 피보나치 수열을 자바 함수로 만든 2번째 버전과 동일하다.)

public int fibonacci(int n, int[] r) {
	if(n <= 0) return 0;
	else if (n == 1) return r[n] = 1;
	return r[n] = fibonacci(n-1, r) + fibonacci(n-2, r);
}

public int fibonacci(int n) {
	if(n <= 1) return n;
	else return fibonacci(n-1) + fibonacci(n-2);
}

---

시간과 메모리 측정

다음은 자바의 기본 정렬 코드의 시간과 메모리를 측정하는 코드다. 자바의 기본 정렬 알고리즘은 ‘듀얼 피벗 퀵 알고리즘’을 사용하며, 평균 시간 복잡도 O(NlogN), 최악의 경우 시간 복잡도는 O(N2)이다.

01. 수행 시간 측정

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        
        int []arr = new int [100_000_000];
        
        for(int i=0; i<100_000_000; i++) {
            arr[i] = (int) Math.random();
        }
        
        long before = System.currentTimeMillis(); //코드 실행 전 시간
        
        //실행할 소스코드
        Arrays.sort(arr);
        
        long after = System.currentTimeMillis(); // 코드 실행 후 시간
        long diff = (after - before); //두 시간에 차이
        System.out.println("시간차이(밀리세컨즈) : "+diff);
        
    }
}

02. 메모리 사용량 측

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        
        int []arr = new int [100_000_000];
        
        for(int i=0; i<100_000_000; i++) {
            arr[i] = (int) Math.random();
        }
        
        // Garbage Collection으로 메모리 초기화
        System.gc();
        
        
        // 실행전 메모리 사용량 조회
        long before = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        System.out.println("Used Memory : " + before);
        
        
        // 프로그램 소스코드
        Arrays.sort(arr);
        
        // Garbage Collection으로 메모리 정리
        System.gc();
        
        // 실행 후 메모리 사용량 조회
        long after = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        
        // 메모리 사용량 측정
        long usedMemory = (before - after)/1024;
        
        System.out.println("Used Memory(MB): " + usedMemory);
        
    }
}

---