본문 바로가기

빅오2

[Extra] 순차탐색 이진탐색 순차탐색(Sequential search) 선형 탐색(Linear search)이라고도함전제조건 : 없음 (정렬되지 않은 리스트여도됨)방법 : 찾을 숫자를 처음부터 나올때 까지 비교함 ex) 1-20중 숫자 고르기 (19) source)int j = [찾을 숫자] int[] arrList; for(int i = 0; i < arrList.length; i++){if (arrList[i] == j){return i;}} 빅오 표기법 : O(N) 이진탐색 (Binary search) 전제조건 : 정렬된 데이터방법 : 정렬된 데이터 집합을 이분화하면서 탐색하는 방법 (관계 없는 1/2을 제외시킴) ex) 1-20중 숫자 고르기 (19) 빅오 표기법 : O(log N) * 반씩 잘라서 찾아나가는것 "이진탐색"*.. 2018. 3. 16.
[Extra] Big-O(빅오 표기법) Big-O (빅오 표기법) - 프로그램의 시간 복잡도를 표기하는 방법- 알고리즘의 성능을 표현하기 위해 사용 빅오 적용법 1. 입력값을 확인하여 무엇을 N 으로 놓을지 정함2. 알고리즘에서 수행할 연산 횟수를 N의 식으로 표현3. 차수가 가장 높은 N만 남김4. 모든 상수인수를 없앰(ex. O(n^2/2) -> O(n^2)) 빅오 성능순서 0. O(1) (성능순서에 제외)- 상수 실행 시간- 항상 일정한 시간에 완료 되지만 현실적으로 거의 없는 알고리즘 1. O(log N)- 로그 알고리즘- 실행시간이 입력크기의 로그에 비해 늘어남- 일반적으로 좋은 효율의 알고리즘 2. O(N)- 선형 알고리즘- 실행시간이 입력크기에 비례하여 늘어남 3. O(N log N)- 초선형 알고리즘- 처리 데이터의 양이 늘 수.. 2018. 3. 11.