1일 1로그 100일 완성 책을 읽으면서 조금씩 정리해놓으려고 한다. 조금 읽어 봤는데 정말 도움된다. 그리고 동시에 비IT인들도 쉽게 이해 가능할듯. 책 좋당.
알고리즘
결과가 정확히 계산되도록 보장된 일련의 단계로 , 각 단계는 명확한 기본 연산으로 이루어져있다. 상상력이 없는 개체가 수행하더라도 연산의 의미와 수행 방법에 이견이 없을 정도로 상세하고 정확하게 이루어져야 한다.
선형 알고리즘
계산 시간이 데이터의 양에 정비례하거나 선형적으로 비례할 때.
초기화를 하고, 각 항목을 차례로 검사하고 간단한 계산을 수행한다는 비슷한 꼴을 가지고 있음
복잡도는 데이터 수에 비례함 : N이진 검색
확인 또는 비교 단계를 거치면서 항목 들이 두 그룹으로 나뉘고 한쪽 그룹은 다음 대상에서 고려 제외할 수 있다.
복잡도는 밑이 2인 로그에 비례함. : log2n
중요한 건 아무리 데이터 수가 늘어도 계산 시간이 천천히 증가한다는 것선택 정렬과 퀵 정렬
선택 정렬의 경우, 첫번째 값을 두번째 값부터 마지막 값까지 비교해서 첫번째 값을 정하고 그 다음엔 두번째 값부터 같은 방식 반복한다. 복잡도는 데이터의 제곱 : n^2 데이터가 조금 늘어날때마다 계산 시간이 너무 많이 소요된다.
퀵 정렬은 한번 훑어보면서 두 그룹으로 나누고, 그 그룹내에서 또 나누고 나누면서 정렬하는 방법이다.
복잡도는 nlog₂n
각 소스 구현한건 나중에 추가하겠다.