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

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번 실행

안녕하세요 햄스터님! 좋은 질문 감사합니다

프사와 닉네임이 너무 귀엽네요

사실상 첫 번째 코드는 이중 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)으로 볼 수 있습니다

또 궁금하신 점이 생기시면 편하게 질문 부탁드립니다 __

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

1. 현재 학습 진도

2. 어려움을 겪는 부분