시간 복잡도란?

시간 복잡도란?

입력값과 연산 수행 시간의 상관관계를 나타내는 척도

시간 복잡도 표현 방법

최상의 경우: 오메가 표기

평균의 경우: 세타 표기

최악의 경우: 빅오 표기  // 시간복잡도의 기준

시간 복잡도 단계

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

O(1) 상수 시간 : 문제를 해결하는데 오직 한단계만 처리 

public static void callFirstStudent(String[] students) {
    if (students.length > 0) {
        System.out.println("첫 번째 학생: " + students[0]);
    }
}

출석부에서 첫번째 학생의 이름을 부르는것과 같다 (즉시 출력값을 얻을수 있는것)

O(log n) 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬

public static boolean findStudentByHeight(int[] heights, int targetHeight) {
    int left = 0;
    int right = heights.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (heights[mid] == targetHeight) {
            return true;
        } else if (heights[mid] < targetHeight) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

키순서로 줄 세운 학생들 중에서 특정 키의 학생을 찾는 로직 (어떤 기준을 갖고 탐색하는것)

O(n) 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n 이 1:1 관계를 가짐

public static int countStudentsWithGlasses(boolean[] hasGlasses) {
    int count = 0;
    for (boolean wearGlasses : hasGlasses) {
        if (wearGlasses) {
            count++;
        }
    }
    return count;
}

교실에서 안경 쓴 학생 수를 세는 로직, 모든 학생을 한번씩 봐야함 ( 1:1로 n번 실행)

O(n log n) 선형로그형 : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번 만큼의  수행시간을 가짐

// 실제 구현은 더 복잡하지만, 개념을 단순화
public static void organizeTeams(String[] students) {
    // 학생들을 무작위로 섞기
    shuffleStudents(students);
    
    // 팀 나누기
    for (int i = 0; i < students.length; i++) {
        assignToTeam(students[i]);
    }
}

체육 수업에서 학생들을 섞은뒤 다음 팀으로 나누는 것과 비슷( 정렬 알고리즘 )

O(n^2) 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱

public static void pairStudentsForProject(String[] students) {
    for (int i = 0; i < students.length; i++) {
        for (int j = i + 1; j < students.length; j++) {
            System.out.println(students[i] + "와 " + students[j] + "가 팀");
        }
    }
}

모든 학생들을 둘씩 짝지어 프로젝트 팀을 만드는 것과 같음. 각 학생마다 다른 모든 학생과 짝을 지어봐야 해서 시간이 오래 걸림 (이중 for문을 사용하여 문제를 풀경우)

시간 복잡도를 구하는 요령

O(n) - 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우

O(n/2) -> O(n) - 컬렉션의 절반 이상을 반복하는 경우

O(n+m) -> O(n) - 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우

O(n^2) - 두 개의 중접 루프를 사용하여 단일 컬렉션을 반복하는 경우

O(n*m) -> O(n^2) - 두 개의 중첩 루프를 사용하여 두개의 다른 콜렉션을 반복할경우

O(n*log n) - 컬렉션 정렬을 사용하는경우

 

참조블로그

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

https://blog.chulgil.me/algorithm/

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