[이코테] chap 1.3 복잡도

복잡도

알고리즘의 성능을 나타내는 척도
크게 아래 2가지를 의미하며, 둘은 trade-off 관계를 가진다.

• 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양

시간 복잡도

• 시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다.
  간단히 정의하면, 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

  • 예로 아래 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간을 O(N) 으로 표기한다.

    array = [3, 5, 1, 2, 4]
    summary = 0
    
    for x in array:
        summary += x
    
    print(summary) #15

시간 복잡도의 표
<table>
  <tr>O(1)</tr>
</table>