Developer Cafe

정렬 알고리즘 중 기본인 버블 정렬의 사용법 1. 배열 내에서 연속된 두 항목을 가르킨다. 2 1 3 5 2. 두 항목의 순서가 바뀌었으면(왼쪽값이 오른쪽값보다 크면) 항목을 바꾼다 1 2 3 5 3. 포인터를 한칸 이동하여 반복한다. 1 2 3 5 1 ~3 을 반복하는 것을 패스스루 라고 한다. 패스스루가 끝나면 마지막 원소 즉, 5를 빼고 다시 패스스루를 반복한다. (총 행의 수 - 1 ) 의 패스스루를 반복한다. 위의 예시에선 3번의 패스스루가 일어난다. 위에 예시에선 결국 (N-1) + (N-2)...+ 1번의 비교를 수행한다. 위의 예시에선 3+2+1=6번의 비교가 일어난다. 여기에 더해 만약 모든 수가 역순일경우엔 총 6번의 교환이 더 일어나게 된다. 총 12단계의 작업이 일어난다. 원소 N개..

빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다. 원소수에 따라 단계가 비례하며 증가한다면 O(N) 빅 오 엔 으로 표기한다. 이를 선형 시간 이라고도 부른다. 원소수가 어떻든 단계가 1이면 O(1)빅 오 일(상수 시간 이라고도 부른다), 단계가 4이면 O(4) 으로 표기한다. 이진 검색에선 O(log N)오 로그 앤으로 표기한다. 즉, 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 방법이다. ex) O(log 4)란 사실 O(log 2^4) 라는 뜻이다. 결국 최종적으로 2로 2단계란 뜻이다. 가장 효율적인 순서론 O(1) > O(log N) > O(N) 이다. 원소개수(N) O(N) O(log N) 8 8 3 16 16 4 32 32 5..

정렬된 배열([1, 3, 5, 9, 15])은 삽입, 삭제가 일반 배열([3, 5, 1, 15, 9])보다 거쳐야 되는 단계수가 더 많다. 그러나 선형검색(인덱스0부터 차례차례)대신 이진검색(100의 중앙 50찾고 50중앙 25찾고 점점 찾고자하는 값에 절반을 날려 단계수가 대폭 줄어듬)을 사용할 수가 있다. 결론 : 만들고자하는 서비스에 사용될 알고리즘이 데이터 검색은 거의 없고, 데이터를 추가하기만 한다면 일반 배열이 더 나을 수 있으나, 검색 기능이 더 많은 서비스를 구현할때는 정렬된 배열이 훨씬 낫다.

1. 배열의 인덱스는 0부터 시작하며 인덱스 0의 메모리 주소는 1010이다. 2. 인덱스 3은 인덱스 0부터 정확히 세 슬롯 뒤에 있다. 3. 따라서 인덱스 3을 찾으려면 1010+3인 1013 메모리 주소로 간다.