본문 바로가기

시스템개발/자료구조랑알고리즘공뷰7

선택 정렬, Selection Sort 입력 : 같은 타입의 변수를 가진 배열 출력 : 해당 타입의 오름차순 / 내림차순에 따른 정렬된 배열 빅오 표기법 : O(n^2) *빅오 표기법에 대해. O(n) : 모든 원소를 한 번씩 건드려야 한다는 뜻. 예) 가수 목록에서 가수를 찾아보자. 이 중 가장 연주 횟수가 가장 많은 가수를 찾기 위해선 모든 항목을 점검해야함. -> 모든 항목을 점검하므로 O(n), 이를 n번 반복해서 목록을 정렬해야함. => O(n) #javascript var list = [3,55,1,33, 44, 20, 9, 7, 15, 49]; console.log("Before Selection Sort : " + list); console.log("After Selection Sort : "); console.log(selec.. 2019. 5. 19.

단순 탐색, Simple Search 입력 : 정렬된 배열 출력 : 정렬된 배열에서 찾는 원소가 존재하면 해당 인덱스, 없으면 null. 빅오표기법 : O(n) #javascript //정렬된 배열 var list=[1,2,3,4,5,7,10,33,57]; //찾고자 하는 값 var search = 57; function simpleSearch(_list, find) { var idx = -1; for(var i = 0 ; i < _list.length; ++i) { if( _list[i] == find) { idx = i; break; } } return idx; } console.log("Simple Search : " + simpleSearch(list, search)); 코드가 간단하지만. 최악의 검색방법이다. 만약 1억개의 이름이 .. 2019. 5. 19.

이진 탐색, Binary Search 입력 : 정렬된 원소 리스트 출력 : 입력받은 원소 리스트에서 찾는 값이 없으면 null을 반환, 찾으면 리스트에서 인덱스(위치)를 반환. 빅오 표기법 : O(log n) #javascript //정렬된 배열 var list=[1,2,3,4,5,7,10,33,57]; //찾고자 하는 값 var search = 33; function binarySearch(list , find) { var start = 0; var end = list.length-1; var cnt = 1; var mid =-1; while(1) { //그냥 나누기 2를 했더니 소수점 값이 출력되어서 idx계산이 안되더라. //강제로 형변환. mid = parseInt((start+end)/2); //해당 배열의 가장 중간값을 선택. v.. 2019. 5. 19.

이전 1 2 다음

티스토리툴바