알고리즘 - 기초

자료구조

• 자료구조란 데이터를 조직하는 방법이다.

• 자료구조의 연산이 얼마나 빠른지 측정하는 경우 시간 관점이 아닌 단계의 관점에서 보아야한다. 즉, 시간복잡도 측면에서 봐야한다는 것이다.

• 컴퓨터는 모든 메모리 주소에 한 번에 접근이 가능하지만 그 메모리 주소에 어떤 값이 있는지 바로 알 수 없다. 따라서 배열의 인덱스값을 찾는 경우보다 그 배열의 값이 어떤 인덱스인지 찾는 경우가 더 많은 단계를 소모한다.

• 즉 , 배열의 값이 어떤 인덱스인지 찾는 경우와 같이 컴퓨터가 한 번에 한 셀씩 확인하는 방법을 선형 검색이라한다.

• 집합은 중복 값을 허용하지 않는 자료이다.

• 따라서 집합배열의 경우 데이터를 등록/삭제하는 경우에는 검색 후 작업이 이루어지기 때문에 일반배열보다 단계가 더 많아진다.

빅 오

• 빅 오는 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.
• 따라서 항상 3단계가 걸리는 알고리즘의 빅 오로 표기하면 O(3)이 아닌 O(1)이다
• 또한 빅 오 표기법은 일반적으로 최악의 시나리오(가장 오래 걸리는 단계)를 가정하여 표기한다.
• 이진검색과 같이 데이터가 두 배로 증가하면 한 단계씩 늘어나는 알고리즘은 O(logN)으로 표기한다. N을 2로 몇번 나눠야1이 되는지를 나타내는것이다.
• 즉 O(log8)의 경우 8을 2로 3번 나눠야 1이 되므로 O(log8) = 3이다.