JAVA 알고리즘 시간복잡도 빅오, 빅오메가, 빅세타

✅ 시간 복잡도의 주요 표기법(Big-O)

표기	명칭	의미	예시상황
O(1)	상수 시간	입력 크기와 무관하게 실행 시간 고정	배열의 인덱스 접근
O(log n)	로그 시간	입력 크기가 커질수록 조금만 증가	이진 탐색
O(n)	선형 시간	입력 크기에 비례해 실행 시간 증가	배열 한 번 순회
O(n log n)	로그 선형 시간	분할+정복 알고리즘	병합 정렬, 퀵 정렬 평균
O(n²)	2차 시간	이중 루프 등	버블 정렬, 이중 for문
O(2ⁿ), O(n!)	지수/팩토리얼 시간	입력 크기 증가에 따라 급격히 시간 증가	완전 탐색, 순열 생성

---

🔍 코드 분석 – 시간 복잡도

public class timeComplexityExample1 {
    public static void main(String[] args) {
        //1~100번째 사이 값 랜덤 선택
        int findNumber = (int)(Math.random() * 100); // O(1)
        for (int i = 0; i < 100; i++) {               // O(n) where n = 100
            if (i == findNumber) {
                System.out.println(i);               // O(1)
                break;
            }
        }
    }
}

 

---

✅ 핵심 동작 요약

• findNumber는 0~99 중 하나의 난수 (100개의 정수 중 하나)
• for문은 i == findNumber가 될 때까지 최대 100회 반복
• if 조건이 참이면 System.out.println(i) 출력 후 break

---

✅ 시간 복잡도 분석

1. 최악의 경우 (Big-O)

• findNumber == 99일 경우, for문은 0부터 99까지 총 100번 돔
• ⇒ O(n), 여기서 n = 100 (하드코딩된 값이지만 일반적으로 n으로 표현)
• 연산 수는 n에 비례하므로 최악 시간 복잡도는:
  ✅ Big-O: O(n)

---

2. 최선의 경우 (Big-Ω)

• findNumber == 0이면 i == 0일 때 바로 종료 (딱 한 번만 돎)
• ⇒ Ω(1)
  ✅ Big-Omega: Ω(1)

---

3. 평균적인 경우 (Big-Θ)

• findNumber는 난수이고, 0~99에서 균일하게 분포된다고 가정하면
• 평균적으로 n/2 = 50번 정도 반복할 것으로 예상
• ⇒ Θ(n) (상수 생략)
  ✅ Big-Theta: Θ(n)

---

📌 상세 설명:

1. int findNumber = (int)(Math.random() * 100);
   → 상수 시간 작업입니다. 랜덤 숫자 하나 생성이므로 O(1).
2. for (int i = 0; i < 100; i++)
   → 반복문이며 최악의 경우 i == 99까지 반복해야 하므로 **O(n)**입니다. 여기서 n은 100이라는 고정값이긴 하지만, 일반적인 시간 복잡도 표기법은 입력 크기 기준으로 일반화하기 때문에 **O(n)**이라 표현합니다.
3. if (i == findNumber) + System.out.println(i);
   → 이 조건문과 출력도 한 번의 연산이므로 **O(1)**입니다.

---

✅ 이 코드의 전체 시간 복잡도는?

📌 O(n)

• 이유: findNumber가 어디에 위치하느냐에 따라 루프가 최대 n번 돌 수 있으므로, 최악의 경우에 대한 시간 복잡도는 **O(n)**입니다.

비록 n = 100으로 고정된 값이라도, 시간 복잡도 표기에서는 입력 크기에 따른 일반적 성능을 나타내기 때문에 **O(n)**이라고 표기합니다.

상수시간 O(1)이라고 하지 않는 이유는 n이 10, 1000, 1억으로 바뀌었을 때 성능이 비례적으로 증가하기 때문입니다.

---

✅ Tip: 평균 시간 복잡도

• findNumber가 무작위라면 평균적으로는 중간쯤(약 50)에서 발견됩니다.
• 이 경우 **평균 시간 복잡도는 O(n/2)**지만, 빅오 표기법에서는 상수는 생략하므로 여전히 **O(n)**으로 표현합니다.