이 알고리즘의 big-O 표기법은 무엇입니까?

Question

현재 동적 프로그래밍을 이해하려고합니다. 흥미로운 문제를 발견했습니다. "nxn 사각형과 시작 위치 (xs, ys)의 체스 보드를 사용하면 가장 짧은 (이동 횟수와 마찬가지로) 경로를 찾을 수 있습니다. 기사는 끝 위치 (xe, ye)에 "가지고 갈 수있다. 이것은 내 솔루션이 다음과 같이 들리는 방식입니다.

Initialize the matrix representing the chess board (except the "square" xs,ys) with infinity. 
The first value in a queue is the square xs,ys. 
while(the queue is not empty){ 
     all the squares available from the first square of the queue (respecting the rules of chess) get "refreshed" 
     if (i modified the distance value for a "square") 
        add the recently modified square to the queue 
} 

이 기능의 컴퓨팅 시간 값은 무엇입니까? 나는 (일종의) big-O를 이해하지만이 함수에 대한 가치를 부여 할 수는 없습니다.

Answer 1

대기열을 사용 중이므로 사각형을 처리하는 순서가 최소 거리 순서대로 이루어집니다. 즉, 정사각형의 거리 값을 한 번만 수정하면 n^2 개의 정사각형이 있으므로 시간은 O (n^2)가됩니다.

Answer 2

Dijkstra의 최단 경로 알고리즘과 다소 유사합니다. 어떤 경우에는 O (N^2)입니다. 가장 낮은 경로를 결정하기 위해 소스에서 대상까지 가능한 모든 경로에 대해 "거리"를 찾습니다.

Answer 3

알고리즘 당신은 당신의 "큐"당신이

를 "새로 고침"정의하지

당신은 항상 첫 번째 광장에 붙어있는 내용을 정의하지 제대로

을 모호하게한다 , 당신은 현재 광장을 추적하고 있지 않습니다.

또한 Google Djkistra의 알고리즘 아니요, dijkstra의 알고리즘을 사용하지 마십시오. 가중 그래프가 없습니다.

동적 프로그래밍 알고리즘을 사용하여 무언가를 무작위로 풀고 싶다면 (xe, ye)부터 시작하면 nxn 모눈에서 O (n^2)를 얻을 수 있어야합니다.

하지만 당신은 당신의 제약을 고려한다면 (당신의 조각 기사처럼 이동하고, 그가 그리드를 따라 이동, 그리고 임의의 그래프)는 O에서이 문제를 할 수 있어야 (n)의 시간

Answer 4

이를 제 생각에는 폭 넓은 첫 번째 검색입니다. 대기열에 최대 한 번 정사각형을 추가하면 대기열 항목의 처리는 O (1)이므로 전체 복잡도는 O (N^2)로 제한됩니다. 그러나 NxN 체스 보드에서 위치 A에서 B로 이동하는 횟수가 N보다 적다는 직설법을 증명할 수 있다면 (직관적으로 N equals 또는 8보다 큰 경우), 알고리즘은 다음과 같이됩니다. 에).