시간복잡도:

시간복잡도란?

알고리즘을 풀고, 시간복잡도 라는 키워드를 많이 사용하지만, 개념자체를 설명할 정도는 알지못했던 것 같다. 설명할 기회가 있었는데 순간 생각이 안나서 잘 모르겠다고 해버린게 너무 아쉽다…. 그래서 다시 공부!!

시간복잡도(Time Complexity)는 입력 크기(n)에 따라 알고리즘이 얼마나 많은 연산을 수행하는지를 수치화한 것 쉽게 말하면, 입력이 커질수록 얼마나 느려지는지를 알려주는 기준

---

왜 중요한가?

• 코드가 맞다고 해서 좋은 알고리즘은 아니다.
• 빠른 코드가 좋은 코드
• 입력 데이터가 작을 땐 상관 없지만, 백만 개, 천만 개가 되면 시간초과가 나기 쉽다.
• 그래서 시간복잡도가 낮을수록 빠르고 효율적인 알고리즘

---

시간복잡도 표기법 (Big-O)

표기	이름	예시	설명
O(1)	상수 시간	arr[0]	입력 크기에 상관없이 항상 같은 시간
O(log n)	로그 시간	이진 탐색	반씩 줄어들며 찾는 방식
O(n)	선형 시간	선형 탐색	전체를 한 번씩 다 확인
O(n log n)	로그-선형	병합 정렬, 퀵 정렬 평균	n번 반복하면서 log n 단계 처리
O(n²)	이차 시간	버블 정렬, 선택 정렬	이중 반복문
O(2ⁿ)	지수 시간	피보나치 재귀	입력이 커질수록 기하급수적으로 증가
O(n!)	팩토리얼 시간	순열	모든 경우의 수 탐색

---

예시

// O(1)
func printFirst(_ arr: [Int]) {
    print(arr[0])
}

// O(n)
func printAll(_ arr: [Int]) {
    for num in arr {
        print(num)
    }
}

// O(n^2)
func printPairs(_ arr: [Int]) {
    for i in arr {
        for j in arr {
            print(i, j)
        }
    }
}

---

실전에서 왜 중요한가?

• 코딩 테스트에선 시간 제한이 있음.
• 그래서 O(n^2)이면 n이 10,000 이상 되면 거의 무조건 시간 초과!!
• 반대로 O(n log n)이면 n이 1,000,000이어도 잘 돌아가게됨.

---

정리

• 시간복잡도는 알고리즘 효율을 판단하는 핵심 기준
• 같은 기능을 하는 코드라도 시간복잡도에 따라 실행 속도가 크게 달라진다.
• 실무에서는 성능 튜닝, 코딩테스트에선 시간 내 통과를 위해 꼭 신경 써야 한다.

---