Алгоритм с O (n log n) временем и O (1) пространственная сложность vs O (n) время и O (n) пространственная сложность

Ответ 1

Не тестируя ничего (рискованное движение!), я буду утверждать, что O (n log n) -time, O (1) -пространственный алгоритм, вероятно, быстрее, чем O (n) -time, O (n) -пространственный алгоритм, но по-прежнему, вероятно, не является оптимальным алгоритмом.

Во-первых, позвольте говорить об этом с точки зрения высокого уровня, который игнорирует конкретные детали описываемых алгоритмов. Одна деталь, о которой следует помнить, состоит в том, что хотя алгоритмы O (n) -time являются асимптотически быстрее алгоритмов O (n log n), они только быстрее логарифмическим фактором. Имея в виду, что число атомов во Вселенной составляет около 10 ⁸⁰ (спасибо, физика!), Log-base log 2 атомов во Вселенной составляет около 240. С практической точки зрения, это означает, что вы можете думать об этом дополнительном коэффициенте O (log n) как о константе. Следовательно, чтобы определить, будет ли алгоритм O (n log n) более быстрым или медленным, чем алгоритм O (n) на конкретном входе, вам нужно будет узнать больше о том, какие константы скрыты нотой большого О. Алгоритм, который работает во времени 600n, будет медленнее алгоритма, который запускается во времени 2n log n для любого n, который подходит, например, в юниверсе. Поэтому, с точки зрения производительности настенных часов, чтобы оценить, какой алгоритм работает быстрее, вам, вероятно, потребуется немного профилировать алгоритм, чтобы узнать, какой из них быстрее.

Затем возникают эффекты кеширования и локальности ссылки. В памяти компьютера имеется огромное количество кэшей, которые оптимизированы для случая, когда считывания и записи расположены рядом друг с другом. Стоимость промаха в кеше может быть огромной - в сотни или тысячи раз медленнее, чем хитом, - поэтому вы хотите попытаться свести это к минимуму. Если в алгоритме используется O (n) память, то по мере увеличения n вам нужно начать беспокоиться о том, как будут плотно упакованы ваши обращения к памяти. Если они распределены, то стоимость промахов в кеше может начать складываться довольно быстро, значительно увеличивая коэффициент, спрятанный в примечании "большой О" временной сложности. Если они более последовательны, вам, вероятно, не нужно слишком беспокоиться об этом.

Вам также нужно быть осторожным в отношении общей доступной памяти. Если у вас 8 ГБ оперативной памяти в вашей системе и получить массив с одним миллиардом 32-разрядных целых чисел, то, если вам нужно O (n) вспомогательное пространство с даже разумной константой, вы не сможете поместиться в свою вспомогательную память в основной памяти, и он начнет выгружаться ОС, действительно убивая ваше время выполнения.

Наконец, проблема случайности. Алгоритмы, основанные на хэшировании, ожидали быстрой работы, но если вы получаете плохую хэш-функцию, есть вероятность, что алгоритм будет замедляться. Создание хороших случайных битов является трудным, поэтому большинство хеш-таблиц просто идут на "разумно хорошие" хэш-функции, рискуя наихудшими входами, что сделает производительность алгоритма вырожденной.

Итак, как эти опасения фактически реализуются на практике? Хорошо, посмотрим на алгоритмы. Алгоритм O (n) -time, O (n) -пространства работает путем построения хеш-таблицы всех элементов в массиве, чтобы вы могли легко проверить, присутствует ли данный элемент в массиве, затем сканирование по массиву и видя, есть ли пара, которая суммируется до общей суммы. Подумайте, как работает этот алгоритм с учетом вышеперечисленных факторов.

• Использование памяти - это O (n), и из-за того, как работает хеширование, обращения к хэш-таблице вряд ли будут последовательными (идеальная хеш-таблица будет иметь довольно много шаблонов произвольного доступа). Это означает, что у вас будет много промахов в кеше.

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

• В результате вышеупомянутых двух факторов постоянный термин, спрятанный в среде выполнения O (n), вероятно, намного выше, чем выглядит.

• Хеширование неэффективно в худшем случае, поэтому могут иметься входы, которые значительно ухудшают производительность.

Теперь подумайте о алгоритме O (n log n) -time, O (1), который работает, выполняя сортировку массива на месте (скажем, heapsort), затем идя внутрь слева и справа и видя если вы можете найти пару, которая суммирует цель. Второй шаг в этом процессе имеет отличную локальность ссылки - практически все обращения к массиву смежны - и почти все промахи кэшей, которые вы собираетесь получить, будут находиться на этапе сортировки. Это увеличит постоянный коэффициент, спрятанный в нотации Big-O. Однако алгоритм не имеет вырожденных входов, а его малый объем памяти, вероятно, означает, что местность ссылки будет лучше, чем подход хеш-таблицы. Поэтому, если бы я должен был догадаться, я бы поместил свои деньги на этот алгоритм.

... Ну, на самом деле, я бы поместил свои деньги на третий алгоритм: O (n log n) -time, O (log n) -пространственный алгоритм, который в основном был описан выше, но с использованием introsort вместо пирамидальная сортировка. Introsort - это O (n log n) -time, O (log n) -пространственный алгоритм, который использует рандомизированную быстродействующую сортировку, чтобы в основном сортировать массив, переключаясь на heapsort, если quicksort выглядит так, как будто оно вырождается, и делает окончательный проход для сортировки очистить все. У Quicksort есть замечательная локальность ссылок - вот почему это так быстро - и сортировка вставки быстрее на небольших входах, поэтому это отличный компромисс. Плюс, O (log n) дополнительная память в основном ничего - помните, на практике log n не более 240. Этот алгоритм имеет лучшую локальность ссылки, которую вы можете получить, давая очень низкий постоянный коэффициент, спрятанный O ( n log n), поэтому он, вероятно, превзойдет другие алгоритмы на практике.

Конечно, я должен также ответить на этот ответ. Анализ, который я сделал выше, предполагает, что мы говорим о довольно больших затратах алгоритма. Если вы только когда-либо смотрите на небольшие входы, то весь этот анализ выходит из окна, потому что эффекты, которые я принимал во внимание, не начнут появляться. В этом случае наилучшим вариантом было бы только проработать подходы и посмотреть, что лучше всего работает. Оттуда вы можете построить "гибридный" подход, когда вы используете один алгоритм для входов в одном диапазоне размеров и другой алгоритм для ввода в другом диапазоне размеров. Скорее всего, это даст подход, который превосходит любой из подходов.

Тем не менее, перефразируя дона Кнута, "остерегайтесь приведенного выше анализа - я просто доказал это правильно, а не попробовал". Лучшим вариантом было бы профилировать все и посмотреть, как это работает. Причина, по которой я не делал этого, заключалась в том, чтобы проанализировать, какие факторы следует обратить внимание, и подчеркнуть слабость чистого анализа большого О, сравнивающего эти два алгоритма. Надеюсь, что практика будет такой! Если нет, я бы хотел увидеть, где я ошибся.: -)

Ответ 2

Из опыта:

• Если вы абсолютно не можете позволить себе пространство, пройдите по маршруту O (1).
• Когда случайный доступ неизбежен, пройдите по маршруту O (n). (Это обычно проще и имеет меньшую постоянную времени.)
• Если произвольный доступ медленный (например, время поиска), направляйте O (1) космический маршрут. (Обычно вы можете определить способ кэширования.)
• В противном случае произвольный доступ выполняется быстро - направьте маршрут O (n). (Обычно это проще с меньшей временной константой.)

Обратите внимание, что обычно произвольный доступ является "быстрым", если проблема помещается в память, которая быстрее, чем хранилище узких мест. (например, если диски являются узким местом, основная память достаточно быстра для случайного доступа --- если основная память является узким местом, кэш процессора достаточно быстр для произвольного доступа)

Ответ 3

Используя ваш конкретный пример алгоритма Array Pair Sum, время хэш-версии O (n) с O (n) будет быстрее. Здесь немного теста JavaScript, с которым вы можете играть с http://jsfiddle.net/bbxb0bt4/1/

Я использовал два разных алгоритма сортировки, быструю сортировку и сортировку по методу radix. Сортировка Radix в этом экземпляре (массив из 32-битных целых чисел) является идеальным алгоритмом сортировки и даже может едва конкурировать с однопроходной хэш-версией.

Если вы хотите получить обобщенное мнение относительно программирования:

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

function apsHash(arr, x) {
    var hash = new Set();
    for(var i = 0; i < arr.length; i++) {
        if(hash.has(x - arr[i])) {
            return [arr[i], x - arr[i]];
        }
        hash.add(arr[i]);
    }
    return [NaN, NaN];
}

function apsSortQS(arr, x) {
    arr = quickSortIP(arr);
    var l = 0;
    var r = arr.length - 1;
    while(l < r) {
        if(arr[l] + arr[r] === x) {
            return [arr[l], arr[r]];
        } else if(arr[l] + arr[r] < x) {
            l++;
        } else {
            r--;
        }
    }
    return [NaN, NaN];
}

Ответ 4

Неверно, что вы всегда можете заменить O (n lg n) время O (1) пространственным алгоритмом, с O (n) временем O (n) пробелом один. Это действительно зависит от проблемы, и существует множество различных алгоритмов с различными сложностями для времени и пространства, а не только линейными или линейными (например, n log n).

Обратите внимание, что пространство O (1) иногда означает (например, в вашем примере), что вам нужно изменить входной массив. Таким образом, это на самом деле означает, что вам нужно O (n) пространство, но вы можете каким-то образом использовать входной массив в качестве своего пространства (в случае использования только постоянного пространства). Изменение входного массива не всегда возможно или разрешено.

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

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

Ответ 5

Чтобы сравнить два алгоритма, во-первых, должно быть совершенно ясно, что мы их сравниваем. Если нашим приоритетом является пространство, алгоритм с T (n) = O (n log n) и S (n) = O (1) лучше. В общем случае второй с T (n) = O (n) и S (n) = O (n) лучше, поскольку пространство может быть скомпенсировано, но время не может.

Ответ 6

При выборе алгоритма следует учитывать три вещи.

• Время, в течение которого приложение будет работать бесперебойно в худшем случае.
• Доступность пространства на основе среды, в которой будет работать программа.
• Повторное использование созданных функций.

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

Если у меня будет ограниченное пространство и разумные данные, предоставленные ему, тогда условие 2 будет играть главную роль. Здесь мы можем проверить гладкость с помощью O(nlogn) и попытаться оптимизировать код и придать значение условию 3. (Например, алгоритм сортировки, используемый в сумме пар массива, может быть повторно использован в другом месте моего кода.)

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

Ответ 7

Предполагая, что ваше предположение верно. Учитывая тот факт, что в реальной жизни неограниченные ресурсы не существуют и что при внедрении решения вы приложите все усилия, чтобы реализовать самое надежное решение (решение, которое не сломается, потому что вы потребляете всю свою разрешенную память), я был бы мудрым и продолжайте:

Algorithm with O(n log n) time and O(1) space complexity

Даже если у вас большой объем памяти, и вы уверены, что никогда не исчерпаете свою память, используя решения, которые потребляют много памяти, могут вызвать множество проблем (скорость чтения/записи ввода-вывода, резервные данные в случае сбоя), и я думаю, что никто не любит приложение, которое использует 2Go памяти при запуске и продолжает расти с течением времени, как если бы была утечка памяти.

Ответ 8

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

здесь простая попытка смоделировать его.
случайные() вызовы функций и mod для временной сложности,
случайный доступ к памяти (чтение/запись) для космической сложности.

#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <math.h>

int test_count = 10;

int* test (long time_cost, long mem_cost){
  // memory allocation cost is also included
  int* mem = malloc(sizeof(int) * mem_cost);
  long i;
  for (i = 0; i < time_cost; i++){
    //random memory access, read and write operations.
    *(mem + (random() % mem_cost)) = *(mem + (random() % mem_cost));
  }
  return mem;
}


int main(int argc, char** argv){
  if (argc != 2) {
    fprintf(stderr,"wrong argument count %d \nusage: complexity n", argc);
    return -1;
  }

  long n = atol(argv[1]);

  int *mem1, *mem2;
  clock_t start,stop;

  long long sum1 = 0;
  long long sum2 = 0;

  int i = 0;
  for (i; i < test_count; i++){
    start = clock();
    mem1 = test(n * log(n), 1);
    stop = clock();
    free(mem1);
    sum1 += (stop - start);

    start = clock();
    mem2 = test(n , n);
    stop = clock();
    free(mem2);
    sum2 += (stop - start);

  }

  fprintf(stdout, "%lld \t", sum1);
  fprintf(stdout, "%lld \n", sum2);

  return 0;
}

отключить оптимизацию;

gcc -o complexity -O0 -lm complexity.c

тестирование;

for ((i = 1000; i < 10000000; i *= 2)); do ./complexity $i; done | awk -e '{print $1 / $2}'

результаты, полученные мной;

7,96269
7.86233
8.54565
8.93554
9.63891
10.2098
10.596
10.9249
10.8096
10.9078
8.08227
6.63285
5.63355
5.45705

до некоторой точки O (n) делает лучше на моей машине,
после некоторой точки O (n * logn) улучшается (я не использовал swap).