알고리즘 & 자료구조/알고리즘 (1) 썸네일형 리스트형 [알고리즘] 시간복잡도(time complexity) 정리 - 코드의 실행 시간이 어떤 요인으로 결정되는지 나타나는 시간과 입력 데이터의 함수 관계. - 빅오(Big-O) 표기법 알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 간의 상관관계 표기 입력 크기가 N이고, 이에 비례하는 시간이 걸린다면 O(N)으로 표기 * 알고리즘과 시간복잡도 알고리즘 시간 복잡도 이진 탐색 O(logN) 선형 탐색 O(N) 정렬 O(N logN) 조합 O(2^N) 순열 O(N!) 고찰 길이가 N이고 정수로 이루어진 배열에서 M개의 숫자 유무를 확인해야 한다고 가정해보자. N은 최대 10,000, M은 최대 100,000일 때, 배열을 전부 순회한다면 시간복잡도는 O(NM) 이므로 10억 이라는 결과가 나온다. 이진 탐색을 이용한다면 O((N+M)logN)의 시간복잡.. 이전 1 다음