알고리즘 분석 이렇게 쉽다고? 최악 vs 평균 vs 최상의 경우 완벽 정리 🔥

알고리즘 분석 이렇게 쉽다고? 최악 vs 평균 vs 최상의 경우 완벽 정리 🔥

 

알고리즘을 분석할 때 우리는 세 가지 주요 사례를 살펴봅니다:

1️⃣ 최악의 경우: 실행 시간이 가장 오래 걸리는 경우
2️⃣ 평균적 경우: 모든 입력에 대한 평균 실행 시간
3️⃣ 최상의 경우: 실행 시간이 가장 짧은 경우

 

이 블로그에서는 간단한 파이썬 예제를 통해 이 개념들을 이해하고, 어떤 상황에서 어떤 분석이 유용한지 알아보겠습니다! 🐍

---

🛠️ 실전 예제: 선형 검색(Linear Search)

📌 문제 설명

주어진 배열에서 특정 값을 찾는 알고리즘입니다. 배열에서 값을 찾을 때, 최악, 평균, 최상의 경우는 다음과 같이 정의됩니다:

• 최악의 경우: 찾고자 하는 값이 배열에 없거나 마지막에 있을 때
• 최상의 경우: 찾고자 하는 값이 배열의 첫 번째 요소일 때
• 평균적 경우: 찾고자 하는 값이 배열의 중간쯤에 있을 때

🔑 파이썬 코드

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 값을 찾으면 인덱스 반환
    return -1  # 값을 찾을 수 없으면 -1 반환

# 배열 예시
arr = [1, 3, 5, 7, 9]
target = 5

# 실행
result = linear_search(arr, target)
print(f"결과: {result} (인덱스)")  # 예상 출력: 2

🕒 시간 복잡도 분석

• 최악의 경우: 배열 전체를 탐색해야 하므로 시간 복잡도는 O(n).
• 평균적 경우: 배열의 절반을 탐색한다고 가정하면, 평균 복잡도도 O(n).
• 최상의 경우: 첫 번째 요소에서 값을 찾으면 O(1).

---

🍎 실전 예제: 주식 가격 합산 프로그램

📌 문제 설명

주식 가격 배열이 주어졌을 때, 다음 조건을 만족하는 프로그램을 작성합니다:
1️⃣ 배열의 길이가 짝수라면 합은 0을 반환합니다.
2️⃣ 배열의 길이가 홀수라면 주식 가격 합계를 반환합니다.

🔑 파이썬 코드

def stock_price_sum(prices):
    n = len(prices)
    if n % 2 == 0:  # 짝수일 때
        return 0
    else:  # 홀수일 때
        return sum(prices)

# 주식 가격 배열
prices1 = [100, 200, 300, 400]  # 짝수 길이
prices2 = [150, 250, 350]  # 홀수 길이

# 실행
print(f"가격 합(짝수): {stock_price_sum(prices1)}")  # 예상 출력: 0
print(f"가격 합(홀수): {stock_price_sum(prices2)}")  # 예상 출력: 750

🕒 시간 복잡도 분석

• 최상의 경우: 배열 길이가 짝수일 때, 시간 복잡도는 O(1).
• 평균적 경우: 짝수와 홀수가 고르게 분포되어 있다고 가정하면 O(n).
• 최악의 경우: 배열 길이가 항상 홀수일 때, 모든 요소를 더해야 하므로 O(n).

🎯 투자 프로그램에서의 활용

1️⃣ 최악의 경우 분석은 주식 검색 및 데이터 처리 알고리즘에서 필수적입니다.

• 예: 급등/급락 주식 검색에서 최악의 경우 데이터를 빠르게 처리할 수 있어야 합니다.

2️⃣ 최상의 경우 분석은 특정 입력만 고려하기 때문에 현실적인 활용은 적습니다.

3️⃣ 평균적 경우 분석은 모든 시나리오를 고려하므로 복잡하지만, 주식 데이터의 분포와 동향 분석에 유용합니다.

 

📌 결론

알고리즘 분석은 주식 프로그램의 효율성을 높이고, 특정 상황에서의 성능을 보장하는 핵심 도구입니다. 🔍