🕰 시간 복잡도 판단하기

• 시간 복잡도란?
  • 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계
• 시간 복잡도 계산하기 (최대값 찾기 예시)

  • 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하면 됨

    input=[3,5,6,1,2,4]
        
    for num in array:                # array 의 길이만큼 아래 연산이 실행
            for compare_num in array:    # array 의 길이만큼 아래 연산이 실행
                if num < compare_num:    # 비교 연산 1번 실행
                    break
            else:
                return num

  • array(입력값)의 길이는 N이라고 표현

  • 즉 위에 연산된것을 더해보면 N * N + 1

  • N²만큼의 시간이 걸렸겠구나 계산 가능

• 두번째 시간 복잡도 계산하기

  input = [3, 5, 6, 1, 2, 4]
  
  def find_max_num(array):
      max_num = array[0] # 연산 1번 실행
      for num in array:  # array 길이만큼 아래 연산 실행
          if num > max_num: # 비교 연산 1번 실행
              max_num = num # 대입 연산 1번 실행
      return max_num

  • 1 + 2 * N

• 위의 표로 깨달아보기

  • N과 N² 은 N 이 커질 수록 더 큰 차이가 남
  • N의 지수를 먼저 비교하여 시간복잡도를 분석하면 좋음
  • 상수는 신경 쓸 필요 없음

• 입력값이란?

  • 함수에서 크기 혹은 길이가 변경 될 수 있는 값

  • 수식으로 표현해야 올바른 알고리즘의 시간 복잡도를 구할 수 있음

    🪐공간 복잡도 파악하기

  • 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계

  • 저장하는 데이터의 양이 1개의 공간을 사용한다

    # 첫번째 방법 공간복잡도 파악  (29개 공간)
    
    input = "hello my name is sparta"
    
    def find_max_occurred_alphabet(string):
        alphabet_array = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t",
                          "u","v","w","x","y","z"] # -> 26개의 공간
    
        max_occurrence = 0 # 1개의 공간
        max_alphabet = alphabet_array[0] #1개의 공간 
        
        
        for alphabet in alphabet_array:
            occurrence = 0 # 1개의 공간
            for char in string:
                if char == alphabet:
                    occurrence += 1
            if occurrence > max_occurrence:
                max_occurrence = occurrence
                max_alphabet = alphabet
                
        return max_alphabet
    
    result = find_max_occurred_alphabet(input)
    print(result)

    # 두번째 방법 공간복잡도 파악   (30개 공간)
    
    def find_max_occurred_alphabet(string):
        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(len(alphabet_occurrence_list)):
            alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간
            if alphabet_occurrence > max_occurrence:
                max_occurrence = alphabet_occurrence
                max_alphabet_index = index
    
        return chr(max_alphabet_index + ord('a'))
    
    result = find_max_occurred_alphabet
    print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
    print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
    print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

    ⁉️ 그러면 공간을 더 적게 쓴 첫번째 방법이 더 효율적일까?

  • 그렇지 않음! 성능에 아무런 차이가 없다!

  • 29와 30 모두 상수라 큰 상관이 없음

  • 시간 복잡도로 비교하면 됨

  • 첫번째 시간복잡도

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

  1. alphabet_array 의 길이 X 대입 연산 1번
  2. alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
  3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)
  4. 위의 연산식 26 (1 + 2 N + 3) = 52N + 104

  • 두번째 시간복잡도

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

  1. string의 길이 X (비교 연산 1번 + 대입 연산 2번)

  2. 대입 연산 2번

  3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)

  4. 위의 연산식 N ( 1 + 2 ) + 2 + 26 ( 1 + 3 ) = 3N + 106

     

     공간복잡도 보단 시간복잡도를 중요하게 생각!

     N²에 비하면 아무것도 아님

     점근 표기법

  • 점근 표기법이란?

  • 알고리즘의 성능을 수학적으로 표현하는 것

    점근 표기법 종류

  • 점근 표기법의 종류에는
    빅오(Big-O), 빅 오메가(Big-Ω)이 있습니다.

  • 빅오(Big-O) : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

  • 빅 오메가(Big-Ω) : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

    def is_number_exist(number, array):
    for element in array:     # array 의 길이만큼 아래 연산이 실행
            if number == element: # 비교 연산 1번 실행 
                return True  # N * 1 = N만큼
        return False
    
    result = is_number_exist
    print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
    print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
    print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

    알고리즘은 사용자의 입력값에 의해 속도가 좌우되기 때문에,

    최선인 빅 오메가보다, 최악인 빅오를 자주 사용하게 될 것

  🍭 알고리즘 문제 접근 기억하기

  1. 입력값에 비례해서 얼마나 늘어날지 파악
  2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민
  3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민