시간 복잡도 / 공간 복잡도

알고리즘의 의미

어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. [표준국어대사전]

• 알고리즘은 좋은 프로그램을 구현하기 위해 필수적이다.
• 하나의 문제도 여러 각도로 문제를 풀 수 있다.

 

시간 복잡도 판단하기

• 시간 복잡도의 의미

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다!

입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이다.

 

계산 방법

바로, 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하시면 됩니다.

    max_num = array[0] # 연산 1번 실행
    for num in array:              # array 의 길이만큼 아래 연산이 실행
        for compare_num in array:  # array 의 길이만큼 아래 연산이 실행
            if num < compare_num:  # 비교 연산 1번 실행
                break
        else:
            return num     
# 1+2\times N

     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번 실행
# 26*(1 + 2*N + 3) = 52N + 104

array(입력값)의 길이는 보통 N이라고 표현합니다.

 

공간 복잡도 판단하기

• 공간 복잡도의 의미

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말합니다! 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이다.

 

계산 방법

저장하는 데이터의 양이 1개의 공간을 사용한다고 계산하시면 됩니다.

    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]
	# -> 26 개의 공간을 사용합니다
    max_occurrence = 0 # 1개의 공간을 사용합니다
    max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다.

    for alphabet in alphabet_array:
        occurrence = 0  # 1개의 공간을 사용합니다       
# 26+9 총 29 만큼의 공간이 사용되었다.

    alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용합니다

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')  # 1개의 공간을 사용합니다
        alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0                   # 1개의 공간을 사용합니다
    max_alphabet_index = 0               # 1개의 공간을 사용합니다
    for index in range(26):
        alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index
# 26+4 총 30 만큼의 공간이 사용되었다.

대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않는다.

따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다.