알고리즘은 "빠르다"와 "느리다" 같은 시간으로 표현하지 않는다
같은 알고리즘이라도 내 컴퓨터가 다른 컴퓨터보다 느릴 수 있기 때문이다.
(i3cpu 보단 i5cpu가 더 빠르겠지?)
같은 문제의 다른사람의 풀이를 보면 나보다 더 짧게, 더 간결하게 제출한 풀이를 본 적이 있다.
답을 도출했다 하더라도 시간초과로 인해 실패하는 경우도 있다.
그러면 지금의 알고리즘 풀이보다 더 효율적인 풀이가 있다는 뜻이다.
이처럼 알고리즘의 속도는 "완료까지 걸리는 절차의 수"로 결정된다.
시간복잡도
입력값의 변환에 따라 코드를 실행할 때, 연산횟수에 비례하여 걸리는 시간이 얼마인가?
간단한 알고리즘은 1초 이내에 실행되지만, 입력값이 점점 커질수록 컴퓨터의 연산시간또한 점점 길어진다.
알고리즘의 시간 복잡도는 이 연산시간을 얼마나 최소화로 구현했는지에 대한 이야기다.
이 시간복잡돈는 빅오 표기법을 사용하여 나타낸다.
O(1)
선형 알고리즘이라고도 하며 n개의 입력이 있을때, n개의 시간이 걸린다는 뜻
데이터의 증가는 성능에 영향을 미치지 않는다.
O(log n)
up & down 게임을 생각하면 된다.
잘 모르겠다면 영상을 보고오자.
노홍철이 적은 1~100 사이의 숫자를 맞추기 위해, 맴버들은 '50보다 up & down'을 물어봤다.
이렇게 절반씩 경우의 수를 줄여 나가며 탐색하는 것을 BST(Binary Search Tree)(이진) 검색이라한다.
절반씩 줄여나가기 때문에 O(1) 다음으로 빠른 시간 복잡도를 가진다.
(n log n)
데이터가 많아질수록 처리시간이 로그많큼 늘어나는 알고리즘
병합정렬, 퀵 정렬이 대표적인 알고리즘이다.
O(n2)
데이터가 많아질 수록 급수적으로 시간이 늘어나는 알고리즘
이중루프가 대표적인 알고리즘이다.
O(2n)
데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘
피보나치 수열이 대표적이며 재귀알고리즘이 해당 될 때도 있다.
O(1) < O (log n) < O (nlog n) < O(n2) < O(2n) 순으로 속도가 느리다
공간복잡도
공간복잡도는 프로그램이 얼마나 많은 공간을 차지 하느냐늘 분석하는 방법이다.
컴퓨터의 발전에 따라 공간복잡도 보다는 시간복잡도의 중요성이 올라갔다.
[Algorithm] 시간 복잡도, 공간 복잡도
[알고리즘] Time Complexity (시간 복잡도)
개발자라면 이제는 알아야하는 Big O 설명해드림. 10분컷.
