Что такое обозначение big-O для этого алгоритма?

Question

В настоящее время я пытаюсь понять динамическое программирование, и я обнаружил интересную проблему: «Учитывая шахматную доску из nxn квадратов и стартовую позицию (xs, ys), найдите кратчайший (как в количестве ходов) путь рыцарь может занять конечную позицию (хе, вы) ". Вот как бы звучало мое решение:

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

Ваш алгоритм плохо сформулирован

Вы не определяете содержимое своей "очереди"

Вы не определяете "обновленную"

вы всегдазастряв на первом квадрате, вы не отслеживаете текущий квадрат.

также, алгоритм Google Djkistra Нет, не делайте алгоритм Dijkstra.у вас нет взвешенного графика.

Если вы хотите использовать алгоритм динамического программирования, чтобы перебрать ваш путь к ответу, я бы начал с (xe, ye), и вы должны иметь возможностьполучить O (n ^ 2) в nxn сетке

, но если вы учитываете свои ограничения (ваша фигура движется как рыцарь, а он движется по сетке, а не произвольному графу), вы сможете сделатьэта проблема за O (n) время

Answer 2

Поскольку вы используете очередь, порядок обработки квадратов будет в порядке минимального расстояния.Это означает, что вы когда-либо измените значение расстояния для квадрата только один раз, и, следовательно, время будет равно O (n ^ 2), поскольку существует n ^ 2 квадратов.

Answer 3

По моему мнению, это первый поиск в ширину. Ясно, что вы добавляете квадрат не более одного раза в очередь, и обработка записи в очереди составляет O (1), поэтому общая сложность ограничена O (N ^ 2). Однако, если вы можете доказать теорему, которая говорит, что число ходов от позиции A до B на шахматной доске NxN меньше, чем N (и интуитивно это звучит разумно, если N равно или больше 8), тогда ваш алгоритм будет O (N).

Answer 4

Похоже на алгоритм кратчайшего пути Дейкстры. В этом случае это O (N ^ 2), вы находите «расстояние» для всех возможных путей от источника до места назначения, чтобы определить самый низкий из них.