시간 복잡도가 얼마나 걸리는지 확인하는 방법

안녕하세요 창민님! 좋은 질문 감사합니다 ㅎㅎ

시간 복잡도를 판단할 때 중요한 것은 입력값 N에 따라 어떻게 실행 시간이 변하는지입니다! 한 번 나눠서 설명드려보겠습니다.

for index in range(len(alphabet_occurrence_array)) 부분 분석:
- alphabet_occurrence_array의 길이는 항상 26(알파벳 개수)으로 고정되어 있습니다.
- 입력 문자열의 길이가 100이든 1000이든, 이 반복문은 항상 26번만 실행됩니다.
- 따라서 이 부분은 O(1)입니다. (상수 시간)
for char in string: 부분 분석:
- 이 반복문은 입력 문자열의 길이(N)만큼 실행됩니다.
- 입력이 커지면 실행 횟수도 비례해서 커집니다.
- 따라서 이 부분은 O(N)입니다.

간단한 예시로 설명해드리겠습니다:

# 예시 1: O(1) - 상수 시간
def example1(n):
    for i in range(10):  # 입력 크기와 관계없이 항상 10번 반복
        print(i)

# 예시 2: O(N) - 선형 시간
def example2(n):
    for i in range(n):   # 입력 크기에 비례해서 반복 횟수 증가
        print(i)

# 예시 3: O(1) - 상수 시간
colors = ['red', 'blue', 'green']  # 고정된 크기
for color in colors:     # 항상 3번만 반복
    print(color)

핵심 규칙:

반복문의 반복 횟수가 입력 크기 N과 무관하게 고정되어 있다면 → O(1)
반복문의 반복 횟수가 입력 크기 N에 비례한다면 → O(N)

따라서 원래 코드에서:

알파벳 배열을 순회하는 부분은 항상 26번 실행 → O(1)
문자열을 순회하는 부분은 입력 길이에 비례 → O(N)

즉, 창민님의 질문인

단순히 변수의 for문이면 n 상수의 for문이면 1 이렇게 생각하면 되는건지 궁금합니다!

을 답변 드리자면, 변수 여부가 아닌 입력값의 길이에 따라 변화하는지가 더 중요하다고 봐주시면 좋을 것 같습니다!

인프런 커뮤니티 질문&답변

1. 현재 학습 진도

2. 어려움을 겪는 부분