컴퓨터 공부하는 블로그 컴퓨터 공부하는 블로그

알고리즘은 효율적으로 짤수록 시간과 자원이 굉장히 줄어드는 효과를 볼 수 있다. 그리고 이러한 알고리즘이 수행하는데 걸리는 시간의 상한선 하한선을 시간복잡도로 표현할 수 있다. 시간복잡도가 낮을수록 해당 알고리즘이 더욱 효율적이라고 볼 수 있다. 시간복잡도에서 알고리즘의 실행시간 상한선은 Big-O 표기법을 사용해 나타낸다. O(1) 상수의 형태 O(log n) 로그 형태 이진 탐색 O(n) 선형 형태 선형 탐색 O(n long n) 선형로그 형태 퀵정렬, 병합정렬(합병), 힙정렬 O(n^c) 다차 형태 선택정렬, 버블정렬, 삽입정렬 해당 표에서는 O(1)가 가장 빠르고 O(n^c)가 가장 오래 걸린다. 이러한 시간 복잡도는 대략적인 큰 숫자를 비교하는 것을 기본으로 한다. 이유는 작은 수를 하나하나 헤..