이진검색 (2) 썸네일형 리스트형 알고리즘 | 정렬 알고리즘의 실행시간 ✔ 학습목표 1. 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Bio O와 Big Ω로 정의할 수 있다. 2. 조건문을 사용해 좀 더 효율적인 알고리즘을 만들 수 있다. 알고리즘의 실행 시간 이제껏 배운 선형 검색(Linear search), 이진 검색(Binary search), 버블 정렬(Bubble sort), 선택 정렬(Selection sort)의 실행시간(시간 복잡도)은 각각 어떻게 되는지 정리해보자. 상한은 다음과 같다. O(1) O(log n) O(n) O(n log n) O(n^2) Linear search o Binary search o Bubble sort o Selection sort o 하한은 다음과 같다. Ω(1) Ω(log n) Ω(n) Ω(n log n) Ω(n^2) L.. 알고리즘 | 검색 알고리즘 ✔ 학습목표 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다. 배열 본 글에서부터는 이제껏 배운 내용(메모리의 구조, 자료형, 배열 등)을 바탕으로 검색이나 정렬과 같은 문제풀이 알고리즘을 학습할 것이다. 이에 앞서 배열 속에서 특정 값을 찾는 방법을 이해해야 한다. 배열은 한 자료형의 여러 값들이 메모리상에 모여있는 구조다. 컴퓨터는 배열을 볼 때 인덱스 하나하나에 접근하게 된다. 이때 어떤 값이 배열에 들어 있는지 확인하는 데는 정렬 여부에 따라 두 가지 방법이 있다. 선형 검색 선형 검색은 순서대로 하나씩 보는 것이다. 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 원하는 값이 들어있는지 확인한다. 50이라는 숫자를 찾는 의사 코드로 예를 들어보자. For i from 0 to n-1.. 이전 1 다음
