Electronic Artist

1. 정렬 방법 별 성능 비교 알고리즘최선평균최악삽입 정렬O(n)O(n^2)O(n^2)선택 정렬O(n^2)O(n^2)O(n^2)버블 정렬O(n)O(n^2)O(n^2)셸 정렬O(n)O(n^1.5)O(n^1.5)퀵 정렬O(nlog_2 n)O(nlog_2 n)O(n^2)힙 정렬O(nlog_2 n)O(nlog_2 n)O(nlog_2 n)합병 정렬O(nlog_2 n)O(nlog_2 n)O(nlog_2 n)기수 정렬O(dn)O(dn)O(dn)      2. 정렬 알고리즘 별 실험 결과 (정수: 60,000개) 알고리즘실행 시간(단위: sec)삽입 정렬7.438선택 정렬10.842버블 정렬22.894셸 정렬0.056힙 정렬0.034합병 정렬0.026퀵 정렬0.014

1. 해싱을 이용한 탐색 다양한 방법으로 구현한 맵의 최고성능은 시간 복잡도 O(logn)이다.그러나, 이보다 더 빠른 탐색시간을 갖는 해싱으로 맵을 구현하면 탐색 연산의 이론적인 시간 복잡도가 O(1)이 된다.   1.1 해싱이란?  해싱은 하나의 문자열을 보다 빨리 찾을 수 있도록 해시 함수에 문자열 입력값을 넣어, 주소에 직접 접근할 수 있는 짧은 길이의 값이나 키 특정한 값으로 추출하는 것을 의미한다.    문자열을 찾을 때, 키값의 문자를 일일이 비교하는 것이 아니라, 문자열에 산술적인 연산으로 해시 키를 계산하여 인덱스(항목이 저장된 위치)에 직접 문자열을 저장해 둔다면, 찾을 때는 한 번의 해시 키 계산만으로 도 쉽게 찾을 수 있게된다.이렇게 키값의 연산에 의해 직접 접근이 가능한 구조를 H..

빅 오(Big O) Computer Scientist들은 서로간에 시간 복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다. 이러한 개념이 빅 오(Big O) 표기법이다. 빅 오(Big O)가 의미하는 것 - 데이터 원소가 N개일 때, 알고리즘에 몇 단계가 필요한가? [배열 읽기에 필요한 단계 수] : O(1) → (N과 무관하게) 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다. [N개 배열의 선형 검색 단계 ] : O(N) → 배열의 선형 검색에는 N단계가 필요하다 [이중 배열의 선형 검색 단계] : O(N^2) → 이중 for문을 사용하므로 N의 2승 단계가 필요하다. 빅 오(Big O)가 나타내는 또다른 깊은 의미 ..