알고리즘

Array 배열 기초개념? 10분안에 정리해줌! - YouTube

검색 알고리즘? 기초개념 잡아드림. 10분 순삭. - YouTube

 

 

 

배열

1. 배열은 연결된 메모리 공간을 사용함.  
2. 따라서, 배열은 빈칸이 없도록 데이터를 유지해야  .
3. 따라서, 연결된 순서값인 index를 가지고 특정위치값을 읽는 'Read'는 쉽지만, 무엇이 들었는지 모르는 중에서 찾아야 하는 'Search'와 공간을 옮겨갸 하는 'Add', 'Delete'는 시간이 많이 걸림.

 

 

탐색

1. 선형 탐색 (Linear Search)

 - 순서대로 탐색하는 것

2. 이진탐색 (Binary Search)

 - 정렬된 배열의 중간값부터 탐색하는 것

 

이진 탐색의 전제조건은 정렬된 리스트-이진탐색이다.
만약, 리스트가 정렬되지 않은 상태라면 정렬x리스트-선형탐색을 쓸 수 밖에 없다.

 

 

Big O 

시간복잡도

- 입력값에 따라 늘어나는 수행 단계가 얼마나 늘어나는지를 표현한 것

 

Big O

 : 선형 시간복잡도 (상수는 표현하지 않는다.)

O(1)

 : 상수(일정 시간) = 인풋 숫자 +n : step 숫자 =1

O(n)

 : 선형 검색 = 인풋 숫자 +n : step 숫자 +n

O(n^2)

 : 2차 시간 = 인풋 숫자 +n : step 숫자 n^2

O(log n)

 : 이진 검색(로그 시간) = 인풋 숫자 +n : step 숫자 n/2

 

* 로그 <ㅡ> 지수

 

 

 

기본 알고리즘

기술 면접 - 손코딩 :: 하고싶은거 다 해 (tistory.com)