시간복잡도 설명부분에서 질문이 있습니다

Question

1. 현재 학습 진도 몇 챕터/몇 강을 수강 중이신가요? 1챕터 7강 (공간 복잡도 판단하기)     2. 어려움을 겪는 부분 1-7 강에서 시간 복잡도 설명을 해주시면서 아래 코드들을 직접 array 길이의 값인 26을 대입하여 비교해주셨는데요, 사실상 첫 번째 코드는 이중 for문이므로 O(N^2)이고, 두 번째 코드는 for문을 각각 1개씩 썼기때문에 O(N)라 시간복잡도면에서 큰 차이가 나지않나해서요 강의에서는 직접 숫자를 대입한 후에 첫 번째 코드와 두 번째코드는 N^2에 비해 효율에 있어 차이가 없다고 말씀하셔서 어디 부분에 제가 혼동이 오는지 궁금하여 질문드립니다!    for alphabet in alphabet_array: # alphabet_array 의 길이(26)만큼 아래 연산이 실행 occurrence = 0 # 대입 연산 1번 실행 for char in string: # string 의 길이만큼 아래 연산이 실행 if char == alphabet: # 비교 연산 1번 실행 occurrence += 1 # 대입 연산 1번 실행 if occurrence > max_occurrence: # 비교 연산 1번 실행 max_alphabet = alphabet # 대입 연산 1번 실행 max_occurrence = number # 대입 연산 1번 실행 for char in string: # string 의 길이만큼 아래 연산이 실행 if not char.isalpha(): # 비교 연산 1번 실행 continue arr_index = ord(char) - ord('a') # 대입 연산 1번 실행 alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 max_occurrence = 0 # 대입 연산 1번 실행 max_alphabet_index = 0 # 대입 연산 1번 실행 for index in range(len(alphabet_occurrence_list)): # alphabet_array 의 길이(26)만큼 아래 연산이 실행 alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 max_alphabet_index = index # 대입 연산 1번 실행

딩코딩코 · Answer

안녕하세요 햄스터님! 좋은 질문 감사합니다 프사와 닉네임이 너무 귀엽네요   사실상 첫 번째 코드는 이중 for문이므로 O(N^2)이고, 두 번째 코드는 for문을 각각 1개씩 썼기때문에 O(N)라 시간복잡도면에서 큰 차이가 나지않나해서요 요 내용에 대해서 답변을 드려보겠습니다! 먼저, 이중 for문이 반드시 O(N^2)을 의미하는 것은 아닙니다. 시간 복잡도를 판단할 때는 루프의 실제 반복 횟수와 입력 크기를 고려해야 합니다. 첫 번째 코드를 자세히 살펴보면: for alphabet in alphabet_array: # alphabet_array의 길이는 26 (상수) for char in string: # string의 길이는 N (변수) # 연산들... 여기서 중요한 점은: alphabet_array 루프는 고정된 길이 26을 가집니다. 이는 상수입니다. string 루프는 길이 N으로 변수입니다. 따라서 전체 시간 복잡도는 O(26 * N)이 되며, Big O 표기법에서 상수 26은 제거되므로 결국 O(N)이 됩니다. 이중 for문이라고 해서 무조건 O(N^2)이 아니라, 각 루프의 입력 크기에 따라 달라집니다. 여기서는 외부 루프가 상수이므로 O(N)으로 볼 수 있습니다 또 궁금하신 점이 생기시면 편하게 질문 부탁드립니다 __