-
복잡도Python study/알고리즘 2022. 9. 15. 18:15
서론
최적의 알고리즘을 구현하기 위해서는 시간 복잡도와 공간 복잡도를 고려해야 한다.
그렇다면 시간 복잡도는 무엇이고 공간 복잡도는 무엇일까?
시간과 공간은 이해 할 수 있는 단어인데, 복잡도는 무슨 말이지?
필자는 시간 복잡도와 공간 복잡도 라는 개념을 처음 접했을 때 위 와 같은 생각이 들었다.
우리는 알고리즘 카테고리에 속한 글을 읽고 있다. 즉, 이 글은 알고리즘과 관련이 있다.
복잡도*Complexity는 알고리즘의 성능을 나타내는 척도이다.
복잡도는 시간 복잡도*Time Complexity와 공간 복잡도*Space Complexity로 나눌 수 있다.
복잡도 영문으로는 Complexity 어감에서 오는 느낌으로 어느 정도 의미를 유추할 수 있을 것이다.
복잡하다는 의미를 수치화 한 것이고 Negative 한 어감이다. 이 것이 알고리즘의 성능을 나타내는 척도라면
복잡하지 않을 수록 좋은 성능을 가진다는 것을 유추할 수 있다.
실제로, 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.
시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미하고
공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래관계(Trade-off)가 성립한다.
메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.
이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다.
실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션*Memoization 이란 기법도 존재한다고 한다.
시간 복잡도(Time Complexity)
- 알고리즘을 위해 필요한 연산의 횟수
시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.
빠른 알고리즘은 느린 알고리즘보다 우수하다.
그런데 여기서 한가지 일반적인 사고방식을 벗어나는 개념이 있다. 바로 '빠르다'와'느리다'이다.
우리가 일반적으로 생각하는 빠르다와 느리다 라는 일반적인 개념과는 차이가 있다.
앞서 시간 복잡도 라는 표현을 간단히 설명했지만, 알고리즘의 빠르다 느리다의 개념은 시간으로 표현하지 않는다.
예를 들어 초단위로 표현하지 않는다는 것이다.
같은 알고리즘 이라도 당신의 컴퓨터에서의 수행 속도가 필자의 컴퓨터에서의 수행 속도보다 빠를 수 있다.
왜냐면 컴퓨터라는 하드웨어에 의해서 결정되기 때문이다.
따라서. 알고리즘의 스피드는 완료까지 걸리는 절차의 수 로 결정된다.
예를 들어, 같은 작업을 수행하는 알고리즘이 있는데 5번의 스탭이 필요한 알고리즘이 10번의 스탭이 필요한 알고리즘 보다 우수하다는 의미이다.
시간 복잡도를 표현할 때는 빅오*Big-O 표기법을 사용한다.
간단히 정의하자면 가장 빠르게 증가하는 항 만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타낸다.
다음은 자주 등장하는 시간 복잡도 표인데, 위쪽에 있을수록 더 빠르다.
시간 복잡도에 따라서 부르는 명칭이 있는데 아래에 같이 정리해 두었다.
빅오 표기법 명칭 O(1) 상수 시간(Constant Time) O(logN) 로그 시간(Log Time) O(N) 선형 시간
ex) 선형검색 알고리즘O(NlogN) 로그 선형 시간 O(N*N) N차 시간 = 다차 시간 O(2*N) 지수 시간 * 빅오 표기법이 항상 절대 적인 것은 아니다.
이것을 그래프로 정리를 하자면,아래와 같은 그림이 된다.
BigO 'Python study > 알고리즘' 카테고리의 다른 글
구현 (0) 2021.11.09 그리디 알고리즘 (0) 2021.11.03