무차별 대입 알고리즘 설명

프로그램 작성

Brute Force Algorithms는 마치 단순한 컴퓨팅 능력에 의존하는 문제를 해결하고 효율성을 향상시키기 위해 고급 기술보다는 모든 가능성을 시도하는 간단한 방법입니다.

예를 들어, 각각 0-9 사이의 4 자리 숫자가있는 작은 자물쇠가 있다고 가정 해보십시오. 당신은 당신의 조합을 잊었지만 다른 자물쇠를 사고 싶지 않습니다. 숫자를 기억할 수 없기 때문에 무차별 대입 방법을 사용하여 잠금을 열어야합니다.

따라서 모든 숫자를 다시 0으로 설정하고 번호가 열릴 때까지 0001, 0002, 0003 등 하나씩 시도합니다. 최악의 시나리오에서는 조합을 찾는 데 104 번 또는 10,000 번의 시도가 필요합니다.

컴퓨터 과학의 전형적인 예는 TSP (여행하는 세일즈맨 문제)입니다. 판매원이 전국 10 개 도시를 방문해야한다고 가정 해 보겠습니다. 총 여행 거리를 최소화하기 위해 이러한 도시를 방문해야하는 순서를 어떻게 결정합니까?

무차별 대입 솔루션은 가능한 모든 경로의 총 거리를 계산 한 다음 가장 짧은 경로를 선택하는 것입니다. 영리한 알고리즘을 통해 가능한 많은 경로를 제거 할 수 있기 때문에 특히 효율적이지 않습니다.

무차별 대입의 시간 복잡도는 O (m n ) 이며, 때때로 O (n * m) 로 작성됩니다.. 따라서 무차별 대입을 사용하여 "m"문자 문자열에서 "n"문자 문자열을 검색하려면 n * m 시도가 필요합니다.

알고리즘에 대한 추가 정보

컴퓨터 과학에서 알고리즘은 주어진 문제를 해결하기위한 단계별 절차의 집합입니다. 계산을 수행하거나 데이터를 처리하거나 자동화 된 추론 작업을 수행하도록 알고리즘을 설계 할 수 있습니다.

위키 백과에서 정의하는 방법은 다음과 같습니다.

알고리즘은 한정된 공간과 시간 내에서 함수를 계산하기 위해 잘 정의 된 공식 언어로 표현할 수있는 효과적인 방법입니다. 초기 상태 및 초기 입력 (비어있을 수 있음)에서 시작하여 명령은 실행될 때 유한 한 수의 잘 정의 된 연속 상태를 진행하여 결국 "출력"을 생성하고 최종 종료 상태에서 종료되는 계산을 설명합니다. 한 상태에서 다음 상태로의 전환이 반드시 결정적인 것은 아닙니다. 무작위 알고리즘으로 알려진 일부 알고리즘은 무작위 입력을 통합합니다.

알고리즘이 따라야하는 특정 요구 사항이 있습니다.

  1. 확실성 : 프로세스의 각 단계가 정확하게 설명됩니다.
  2. 효과적인 계산 능력 : 프로세스의 각 단계는 컴퓨터로 수행 할 수 있습니다.
  3. 유한성 : 프로그램은 결국 성공적으로 종료됩니다.

일반적인 알고리즘 유형은 다음과 같습니다.

  • 정렬 알고리즘
  • 검색 알고리즘
  • 압축 알고리즘.

알고리즘 클래스에는 다음이 포함됩니다.

  • 그래프
  • 동적 프로그래밍
  • 정렬
  • 수색
  • 문자열
  • 수학
  • 계산 기하학
  • 최적화
  • 여러 가지 잡다한.

기술적으로 알고리즘 클래스는 아니지만 데이터 구조는 종종 그룹화됩니다.

능률

알고리즘은 가장 일반적으로 작업을 완료하는 데 필요한 컴퓨팅 리소스의 양과 효율성으로 판단됩니다.

알고리즘을 평가하는 일반적인 방법은 시간 복잡성을 확인하는 것입니다. 이것은 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 증가하는 방식을 보여줍니다. 오늘날 알고리즘은 대용량 데이터 입력에서 작동해야하므로 알고리즘이 상당히 빠른 실행 시간을 갖는 것이 필수적입니다.

알고리즘 정렬

정렬 알고리즘은 필요에 따라 다양한 형태로 제공됩니다. 매우 일반적이고 널리 사용되는 일부는 다음과 같습니다.

Quicksort

빠른 정렬없이 끝낼 수있는 정렬 토론이 없습니다. 기본 개념은 다음과 같습니다. 빠른 정렬

병합 정렬

정렬 된 배열을 병합하여 하나의 정렬 된 배열을 제공하는 방법 개념에 의존하는 정렬 알고리즘입니다. 여기에서 더 많은 것을 읽으십시오 : Mergesort

freeCodeCamp의 커리큘럼은 알고리즘 생성을 강조합니다. 학습 알고리즘은 프로그래밍 기술을 연습하는 좋은 방법이기 때문입니다. 면접관은 개발자 면접 중에 알고리즘에 대한 후보자를 가장 일반적으로 테스트합니다.

JavaScript의 알고리즘에 대한 책 :

JavaScript의 데이터 구조

  • JavaScript의 데이터 구조를 다루는 무료 책
  • GitBook

JavaScript 데이터 구조 및 알고리즘 학습-제 2 판

  • 객체 지향 프로그래밍, 프로토 타입 상속, 정렬 및 검색 알고리즘, 빠른 정렬, 병합 정렬, 이진 검색 트리 및 고급 알고리즘 개념을 다룹니다.
  • 아마존
  • ISBN-13 : 978-1785285493

JavaScript를 사용한 데이터 구조 및 알고리즘 : 웹에 고전적인 컴퓨팅 접근 방식 도입

  • 재귀, 정렬 및 검색 알고리즘, 연결 목록 및 이진 검색 트리를 다룹니다.
  • 아마존
  • ISBN-13 : 978-1449364939