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

Question

1. 현재 학습 진도 1-10 듣고 있습니다   2. 어려움을 겪는 부분     이 코드에서 for index in range(len(alphabet_occurrence_array)) 는 N이 아니라 상수이기때문에 O(1)라고 말씀해주셨는데 해당 부분이 잘 이해 가지 않습니다..   for문이라도 정해진 숫자의 범위가 돌면 O(n)의 시간 복잡도가 아닌건가요?   만약 이렇게 이해하게 되면 for char in string: 코드에서 string도 배열에 크기에 정해진 숫자만큼만 돌게 되는데.. 헷갈립니다..!   단순히 변수의 for문이면 n 상수의 for문이면 1 이렇게 생각하면 되는건지 궁금합니다!

딩코딩코 · Answer

안녕하세요 창민님! 좋은 질문 감사합니다 ㅎㅎ   시간 복잡도를 판단할 때 중요한 것은 입력값 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 이렇게 생각하면 되는건지 궁금합니다! 을 답변 드리자면, 변수 여부가 아닌 입력값의 길이에 따라 변화하는지가 더 중요하다고 봐주시면 좋을 것 같습니다!