Поиск лучшего алгоритма (асимптотически) и игнорирование других деталей - PullRequest
Новая
       36

Поиск лучшего алгоритма (асимптотически) и игнорирование других деталей

2 голосов
/ 28 октября 2011

Бывают случаи, когда метод грубой силы в решении проблемы имеет сложность, которая недостаточно хороша с точки зрения производительности.

Давайте возьмем, к примеру, например. Тета (п ^ 2).

Используя рекурсивный подход, он может быть улучшен до Theta (nlogn).

Очевидно, что асимптотически можно было бы использовать рекурсивный подход, поскольку для все большего и большего входного значения N порядок роста ниже, т.е. лучшая производительность.

У меня следующий вопрос:

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

Так как же мы можем быть уверены, что выберем лучший алгоритм для конкретной задачи, если проигнорируем эти детали?

Ответы [ 2 ]

4 голосов
/ 28 октября 2011

Возможно реализовать рекурсивные алгоритмы без использования аппаратного стека.Если возможность переполнения стека представляет серьезную проблему, вы можете реализовать свой собственный стек или просто ограничить глубину рекурсии.

Однако , если алгоритм разделяет набор данных.(размером n) рекурсивно, тогда количество рекурсий будет пропорционально log n.Это означает, что для исчерпания стека размером s вам нужны данные размера порядка 2^s, который очень быстро растет с s.Люди, как правило, не ценят, как быстро растет экспоненциальная функция.Я хочу сказать, что с этим типом алгоритма (разбиение набора данных на каждом рекурсивном шаге) весьма маловероятно, что входные данные могут быть достаточно большими, чтобы потребовать столько рекурсий, чтобы исчерпать стек.

РЕДАКТИРОВАТЬ: Но тогда я не профессиональный программист, поэтому мне не хватает практического опыта фронта.

0 голосов
/ 28 октября 2011

Вот полезный трюк, который я впервые увидел в быстрой сортировке: 

f(x)
{
  for (;;)
  {
    if (x is trivial)
    {
      return;
    }
    x1 = one half of problem x
    x2 = other half of problem x
    if (x1 is the little half)
    {
      x = x2;
      f(x1);
    }
    else
    {
      x = x1;
      f(x2);
    }
  }
}

Суть в том, что каждый рекурсивный вызов составляет небольшую половину проблемы - обычно меньше половины размераисходная проблема - и большая часть проблемы выполняется с помощью итерации.Если проблема имеет размер 2 ^ n, размер стека должен быть только n, даже если - из-за очень неравномерного разбиения - в конечном итоге вы берете время, близкое к n ^ 2, вместо n log n.

Что касается «реальной стоимости» алгоритмов, которые используют n log n времени, но загружают стек, обратите внимание, что алгоритм, который выполняется за время n log n, не имеет времени для использования более n log n памяти, поэтому загружает изагрузка стека на самом деле не может быть огромным объемом памяти, хотя этого может быть достаточно, чтобы, например, интерпретатор Java аварийно завершил работу вашей программы под впечатлением, что у вас убегающая рекурсия.

...