javascript 에서 흔히 볼 수 있 는 간단 한 알고리즘 문제
5351 단어 알고리즘
가장 간단 한 실현
function f1(n){
// i++; //
if(n <= 2) return 1;
return f1(n-1) + f1(n-2);
}
이것 은 가장 간단 한 실현 이지 만, 우 리 는 재 귀 횟수 가 많아 서 메모리 가 매우 소모 되 고, 성능 에 항상 좋 지 않다 는 것 을 안다.그래서 다른 방법 으로 할 수 있어 요.
function f2(n){
var cache = [1,1,1];
function _fn(n){
// i++; //
if(cache[n]) return cache[n];
cache[n-1] = _fn(n-1);
cache[n-2] = _fn(n-2);
return cache[n-1] + cache[n-2];
}
return _fn(n);
}
이 방법 은 주로 가 져 온 값 캐 시 (여 기 는 하나의 배열 로) 를 올 려 서 이 값 을 읽 을 때 캐 시 에서 직접 가 져 오 면 되 고 일부 재 귀 를 줄 일 수 있 습 니 다.상기 두 가지 방법 은 들 어 오 는 n 수치 가 작 을 때 괜 찮 습 니 다. n 의 값 이 조금 만 크 면 첫 번 째 방법 은 바로 무 너 집 니 다.다음은 이들 의 집행 성능 상의 차이 이다. n = 40 시
console.log(f1(40), i, Date.now()-t) // 102334155, 204668309, 2112ms
console.log(f2(40), i, Date.now()-t) // 102334155, 77, 7ms
2. 이분법 찾기
원 리 는 한 단락 의 범위 내 에서 중간 위치의 값 과 찾 으 려 는 값 을 비교 한 다음 에 점차적으로 범 위 를 좁 히 는 것 이다.전제조건 은 배열 이 순서대로 배열 되 어 있다.
아래 코드 는 기본 배열 이 정렬 되 어 있 습 니 다.
/**
* @param {[]} arr
* @param {number} x
* @method ( )
*/
function bsearch(arr, x){
var l = 0; //
var r = arr.length - 1; //
var guess = 0; //
while(l <= r){
//
guess = Math.floor((r + l) / 2);
//
if(arr[guess] === x) return guess;
// ,
else if(arr[guess] > x) r = guess - 1;
// ,
else l = guess + 1;
}
//
return -1;
}
var arr = [1,2,3,34,55,56,89,102,233,345,699,785];
console.log(bsearch(arr, 11)) //-1
console.log(bsearch(arr, 111)) //-1
console.log(bsearch(arr, 345)) //9
console.log(bsearch(arr, 102)) //7
3. 배열 정렬
거품 정렬
사고: 여기 서 예 를 들 어 정렬 하고 배열 에서 인접 한 두 가지 값 을 비교 합 니 다. 만약 에 앞의 것 이 뒤의 것 보다 크 면 교환 위 치 는 한 바퀴 가 비교 하면 최대 치 를 맨 뒤에 얻 을 수 있 고 나머지 는 이렇게 순환 적 으로 비교 할 수 있 습 니 다.
/**
* @param {array} arr
* @method
* @return {array}
*/
function bubbleSort(arr){
//
for(var i=0; i arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
var arr = [1,3,23,54,-9,6,10,99];
console.log(bubbleSort(arr)) //[ -9, 1, 3, 6, 10, 23, 54, 99 ]
정렬 선택
원리: 사실 거품 정렬 과 차이 가 많 지 않 습 니 다. 거품 정렬 은 두 가지 가 서로 바 뀌 지만 정렬 을 선택 하 는 것 은 현재 배열 의 정렬 되 지 않 은 부분 에서 그 최대 치 를 선택 한 다음 에 이 부분의 마지막 으로 이동 하 는 것 입 니 다.예 를 들 어 현재 배열 의 길 이 는 5 이 고 처음으로 이 5 개 중에서 최대 치 를 찾 아 마지막 으로 이동 한 다음 에 나머지 4 개 를 찾 아 최대 치 를 찾 아 이 4 개의 마지막 으로 이동 합 니 다. 이렇게 순환 하면 배열 이 마지막 1 개 만 남 을 때 까지 배열 정렬 후의 첫 번 째 입 니 다.
/**
* @param {array} arr
* @param {number} length
* @method
* @return
*/
function findMax(arr, length){
var max = arr[0], index = 0;
for(var i=1; i= max) {
max = arr[i];
index = i;
}
}
return index;
}
/**
* @param {array} arr
* @param {number} length length
* @method
* @return {array}
*/
function selectSort(arr, length){
// ,
while(length > 1){
//
var index = findMax(arr, length);
var temp = arr[index];
//
arr[index] = arr[length-1];
arr[length-1] = temp;
length--;
}
return arr;
}
var arr = [11,22,23,-9,-23,11,16,23,-9,11,23,56,22];
console.log(selectSort(arr, arr.length)); //[ -23, -9, -9, 11, 11, 11, 16, 22, 22, 23, 23, 23, 56 ]
빠 른 정렬
사고: 두 개의 빈 배열 l 과 r 를 만 들 고 정렬 할 배열 에서 중간 위치 에 있 는 값 centerValue 를 꺼 낸 다음 에 배열 을 옮 겨 다 니 며 현재 값 이 centerValue 보다 작 으 면 l 배열 에 추가 합 니 다. 그렇지 않 으 면 r 배열 에 추가 하고 마지막 으로 배열 은 l, centerValue, r 를 합 쳐 되 돌려 줍 니 다.그리고 함수 재 귀 를 진행 합 니 다.
/**
* @param {array} arr
* @method
* @return {array}
*/
function quickSort(arr){
// length=1 ,
if(arr.length < 2) return arr;
var l = [], r = [];
//
var centerIndex = Math.floor((arr.length - 1)/2);
//
var centerValue = arr.splice(centerIndex, 1)[0];
for(var i=0; i
몇 가지 정렬 효율 비교
정렬 을 선택 하면 거품 정렬 과 비슷 합 니 다.
먼저 length 가 100 인 수치 배열 을 무 작위 로 생 성 합 니 다. 거품 정렬, 빠 른 정렬, 원생 sort 는 차이 가 많 지 않 고 5 ~ 7ms 정도 입 니 다.
length 는 1000 의 수치 배열 로 원생 sort 는 약간 조각 이 있 고 거품 이 나 는 것 과 빠 른 정렬 은 차이 가 많 지 않 습 니 다.
length 는 10000 의 수치 배열 로 원생 sort 와 빠 른 정렬 은 차이 가 별로 없 으 며 약 20 ~ 30ms 로 거품 정렬 이 가장 느 리 고 100 여 ms 가 필요 합 니 다.
length 는 100000 의 수치 배열 로 원생 sort 가 가장 빠 르 고 100 ms 정도 입 니 다.빠 른 정렬 순서, 200 여 ms;거품 정렬 이 가장 느 리 고 10s 정도 (차이 가 매우 크다).
변태 가 왔 습 니 다. 마지막 에 length 는 1000000 에 왔 습 니 다. 원생 이 가장 빠 르 고 800 ms 정도 입 니 다.빠 른 정렬 순서, 3s 정도;거품 정렬 이 바로 튀 었 다.
상기 구체 적 인 시간 수 치 는 기계 환경의 영향 을 많이 받 을 수 있 고 비교 만 할 수 있 으 며 실제 수 치 를 대표 하 는 것 이 아니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.