Задача заправки автомобиля (жадный алгоритм), вложенная, пока l oop со сложностью O (n) - PullRequest
Новая
       67

Задача заправки автомобиля (жадный алгоритм), вложенная, пока l oop со сложностью O (n)

1 голос
/ 07 мая 2020

Введите

(1) максимальное расстояние, которое автомобиль может проехать с полным баком: L км;

(2) целочисленный массив, [0, x1, x2,…, xn, xn + 1], каждое целое число представляет расстояние между местоположением и исходной точкой A. Первое целое число равно 0, что представляет собой расстояние между A и A. Второе расстояние x1 представляет расстояние между первая заправочная станция и A. Между A и B (пункт назначения) n заправочных станций. xn - это расстояние между последней заправочной станцией и A, а xn + 1 - расстояние между B и A.

(3) n, то есть количество заправок.

Выход

Минимальное количество заправок для перехода от A к B

Код 

numRefills = 0
currentPosition = 0

while(currentPosition <= n){
    lastPosition = currentPosition

    while(currentPosition <= n  &&  x[currentPosition + 1] – x[lastPosition] <= L) {
    currentPosition++;
    }

    if (currentPosition == lastPosition) return IMPOSSIBLE; 
    if (currentPosition <= n) numRefills ++;
}

return numRefills

Мои сомнения:

  1. Почему временная сложность приведенного выше кода равна O (n)? Разве это не должно быть O (n ^ 2) хотя бы из-за вложенных циклов while?
  2. Как доказать, что «Заправка на самом дальнем доступном газе» - безопасный ход?
  3. Есть ли какие-нибудь альтернативы написанию того же кода, но с использованием для l oop?

(Короче говоря, я понял logi c, но не могу его вычислить)

Любые ресурсы / помощь / подсказка / руководство приветствуются!

1 Ответ

1 голос
/ 07 мая 2020

Сомнение 1:

Временная сложность рассчитывается по количеству выполненных операций. Неважно, сколько вложенных l oop там ...

Ваше первое while l oop выполнено до currentPosition <= n и вложено, пока l oop выполнено до currentPosition <= n && x[currentPosition + 1] – x[lastPosition] <= L .. В этом l oop вы увеличиваете currentPostion. Таким образом, ваша общая операция не может превысить n раз.

Пример:

array[0, 10, 20, 30] и L = 50 ..

В этом случае ваше первое while l oop true для 1-го шага .. Вы вложили l oop true для 4 шагов. Затем на 2-м шаге ваш первый, пока l oop false ... Итак, был выполнен шаг N ...

Вот почему ваш код сложен: O ( N ) ...

Сомнение 2:

Чтобы минимизировать заправку, вам нужно go как можно дальше с текущим топливом. Если вы пересечете k станцию ​​с текущим топливом, то на 1 to k-1 станциях заправлять бак не нужно .. Каждую станцию ​​вам нужно проверить, возможно ли go на следующую станцию ​​с текущим топливом. Если вы можете go с текущей станции на следующую станцию ​​с текущим топливом, то долить бак на текущей станции будет лишним.

Сомнение 3:

Есть много способов решить проблему .. . Вот еще один: 

numRefills = 0
currentPosition = 0
currentFuel = L
while(currentPosition <= n){
   if (currentFuel < x[currentPosition+1] - x[currentPosition]) {
      currentFuel = L;
      numRefills++;
   }
   currentFuel -= (x[currentPosition+1] - x[currentPostion]);
   if ( currentFuel < 0 ) 
      return Impossible;
   currentPosition++;
}

return numRefills
...