누구나 자료 구조와 알고리즘

2장. 알고리즘이 중요한 까닭

2장에서는 어떤 자료 구조를 이미 결정했더라도 코드의 효율성에 영향을 미칠 수 있는 중요한 요인이 있음을 살펴볼 것이다.

목차

1. 알고리즘이란?
2. 정렬된 배열
3. 이진 검색 대 선형 검색

1. 알고리즘이란?

알고리즘이란 단순히 문제를 해결하는 절차
컴퓨팅 관점에서 알고리즘은 특정 연산을 풀어나가는 절차
때때로 읽기, 검색, 삽입, 삭제의 연산 중 두 가지 이상의 방법을 사용할 수도 있다.

2. 정렬된 배열

값이 항상 순서대로 있어야 한다.
순서가 있으므로 삽입 시 아무데나 할 수 없고 검색 후 삽입
장점: 검색 연산 -> 이진 검색 가능
단점: 삽입 연산

3. 정렬된 배열의 검색: 이진 검색

이진 검색 장점: 선형 검색보다 훨씬 빠르다.
정렬된 배열에서는 항목의 개수를 두 배 늘릴 때마다 이진 검색에 필요한 단계는 1개씩만 증가
선형 검색은 원소 수만큼의 단계가 필요

정렬된 배열은 검색 연산에 강력하지만 삽입 연산은 그냥 배열보다 느리므로 사용자 애플리케이션에 어떤 구조가 더 좋을지 분석하고 선택해야 한다.