알고리즘

시간복잡도

• 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계. 입력값이 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번 실행

위 식에서의 시간복잡도 : (1 + 2*N + 3) = 52N + 104만큼의 시간이 걸린다 라고 생각.
-> N 만큼의 시간 복잡도 ( 매번 코드를 매 실행 단위로 이렇게 몇 번의 연산이 발생하는지 확인하는 건 불가능)

공간복잡도

• 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지.
• 예시 : 선언한 배열의 길이/변수의 개수
• 결국엔 상수이기떄문에 성능에 큰 영향을 미치지않는다.
• 따라서 우리가 신경써야할 부분은 공간복잡도보단 시간복잡도.

점근 표기법

• 알고리즘의 성능을 수학적으로 표기하는 방법.(알고리즘의 "효율성"을 평가하는 법)
• 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현.

점근표기법의 종류

1. 빅오(Big-O) 표기법

• 최악의 성능이 나올떄 어느 정도의 연산량이 나올지.

2. 빅오메가(Big-Ω) 표기법

• 최선의 성능이 나올떄 어느 정도의 연산량이 나올지.
  -> 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석함.
  -> 대부분의 입력값이 최선의 경우일 가능성은 매우적고, 최악의 경우를 대비해야하기떄문.