Вопрос анализа алгоритма
https://stackoverflow.com/questions/1066660
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
ПРИМЕЧАНИЕ:Я новичок в анализе алгоритмов, поэтому не принимайте ни одно из моих утверждений за абсолютную истину, все (или все), что я утверждаю, может быть неправильным.
Привет, я читаю об анализе алгоритмов и «Big-O-Notation» и кое-что озадачил.
Предположим, вас просят распечатать все перестановки массива символов, для [a,b,c] это будут ab, ac, ba, bc, ca и cb.
Ну, один из способов сделать это (на Java):
for(int i = 0; i < arr.length; i++)
for(int q = 0; q < arr.length; q++)
if(i != q)
System.out.println(arr[i] + " " + arr[q]);
Этот алгоритм имеет обозначение На2) если я прав.
Я думал другой способ сделать это:
for(int i = 0; i < arr.length; i++)
for(int q = i+1; q < arr.length; q++)
{
System.out.println(arr[i] + " " + arr[q]);
System.out.println(arr[q] + " " + arr[i]);
}
Теперь этот алгоритм в два раза быстрее оригинала, но если я не ошибаюсь, для большой О-нотации это также О(2)
Это верно?Наверное, это не так, поэтому перефразирую:Где я ошибаюсь??
Решение
Ты прав.О-нотация дает представление о том, как масштабируется алгоритм, а не об абсолютной скорости.Если вы добавите больше возможностей, оба решения будут масштабироваться одинаково, но одно всегда будет в два раза быстрее другого.
Операции O(n) также могут быть медленнее, чем операции O(n^2), для достаточно малого n.Представьте, что ваше вычисление O(n) включает в себя извлечение 5 квадратных корней, а ваше решение O(n^2) представляет собой одно сравнение.Операция O(n^2) будет быстрее для небольших наборов данных.Но когда n=1000, и вы выполняете 5000 квадратных корней, но 1000000 сравнений, тогда O(n) может выглядеть лучше.
Другие советы
Я думаю, большинство людей согласятся, что первый — O(n^2).Внешний цикл выполняется n раз, а внутренний цикл выполняется n раз при каждом запуске внешнего цикла.Таким образом, время выполнения равно O(n * n), O(n^2).
Второй — O(n^2), поскольку внешний цикл выполняется n раз.Внутренние циклы выполняются n-1 раз.В среднем для этого алгоритма внутренний цикл выполняется n/2 раз для каждого внешнего цикла.поэтому время выполнения этого алгоритма составляет O(n * n/2) => O (1/2 * n^2) => O(n^2).
Обозначение Big-O ничего не говорит о скорости алгоритма, за исключением того, насколько быстро он работает относительно самого себя при изменении размера входных данных.
Алгоритм может быть O(1), но на это уйдет миллион лет.Другой алгоритм может быть O(n^2), но он будет быстрее, чем алгоритм O(n) для малых n.
Некоторые ответы на этот Вопрос может помочь с этим аспектом обозначения big-O.Ответы на этот вопрос также может быть полезен.
Игнорирование проблемы вызова вывода вашей программы «перестановка»:
Big-O-Notation опускает постоянные коэффициенты.А 2 – постоянный коэффициент.
Итак, нет ничего плохого в том, что программы в два раза быстрее оригинала имеют один и тот же O().
Ты прав.Два алгоритма эквивалентны в нотации Big O, если один из них требует на постоянное количество времени больше («A занимает на 5 минут больше, чем B»), или кратно («A занимает в 5 раз больше времени, чем B»), или оба («A занимает 2 раза B плюс дополнительные 30 миллисекунд") для всех размеров ввода.
Вот пример, в котором для решения аналогичной задачи используется ФУНДАМЕНТАЛЬНО другой алгоритм.Во-первых, более медленная версия, которая очень похожа на ваш исходный пример:
boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
for (int j = i; j < arr2.length(); j++) {
if (arr1[i] == arr2[j]) {
arraysHaveAMatch = true;
}
}
}
Это имеет поведение O(n^2), как и ваш оригинал (он даже использует тот же ярлык, который вы обнаружили, начиная индекс j с индекса i, а не с 0).Теперь другой подход:
boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
if (set.contains(arr2[j])) {
arraysHaveAMatch = true;
}
}
Теперь, если вы попытаетесь запустить их, вы, вероятно, обнаружите, что первая версия работает БЫСТРЕЕ.По крайней мере, если вы попытаетесь использовать массивы длиной 10.Потому что вторая версия должна иметь дело с созданием объекта HashSet и всех его внутренних структур данных, а также потому, что она должна вычислять хэш-код для каждого целого числа.ОДНАКО, если вы попробуете это с массивами длиной 10 000 000, вы обнаружите СОВЕРШЕННО другую историю.Первая версия должна проверить около 50 000 000 000 000 пар чисел (около (N*N)/2);вторая версия должна выполнять вычисления хеш-функции примерно для 20 000 000 чисел (около 2*N).В ЭТОМ случае вам наверняка нужна вторая версия!!
Основная идея вычислений Big O заключается в том, что (1) их достаточно легко вычислить (вам не нужно беспокоиться о таких деталях, как скорость вашего процессора или тип кэша L2), и (2) кого волнует небольшие проблемы...в любом случае они достаточно быстрые:это БОЛЬШИЕ проблемы, которые убьют вас!Это не всегда так (иногда ДЕЙСТВИТЕЛЬНО имеет значение, какой у вас тип кэша, а иногда ДЕЙСТВИТЕЛЬНО имеет значение, насколько хорошо все работает с небольшими наборами данных), но они достаточно часто близки к истине, чтобы Big O был полезен.
Вы правы в том, что они оба имеют квадрат «большого числа», и вы фактически доказали это в своем вопросе, когда сказали: «Теперь этот алгоритм дважды так же быстро, как оригинал». В два раза быстрее означает умножение на 1/2, что является константой, поэтому по определению они находятся в одном и том же наборе big-O.
Один из способов размышления о «Большом О» — рассмотреть, насколько хорошо будут себя вести различные алгоритмы даже в действительно несправедливых обстоятельствах.Например, если один работал на действительно мощном суперкомпьютере, а другой — на наручных часах.Если можно выбрать настолько большое N, что даже несмотря на то, что на суперкомпьютере работает худший алгоритм, наручные часы все равно могут финишировать первыми, тогда у них будут разные сложности Big O.С другой стороны, если вы видите, что суперкомпьютер всегда будет побеждать, независимо от того, какой алгоритм вы выбрали или насколько велико ваше N, то оба алгоритма по определению должны иметь одинаковую сложность.
В ваших алгоритмах более быстрый алгоритм был всего в два раза быстрее первого.Этого недостаточно для того, чтобы наручные часы превзошли суперкомпьютер. Даже если бы N было очень большим, равным 1 миллиону, 1 триллиону или даже числу Грэма, карманные часы никогда не смогли бы победить суперкомпьютер с таким алгоритмом.То же самое было бы верно, если бы они поменялись алгоритмами.Следовательно, оба алгоритма по определению Big O имеют одинаковую сложность.
Предположим, у меня есть алгоритм, делающий то же самое за O(н) время.Теперь предположим, что я дал вам массив из 10 000 символов.Ваши алгоритмы потребовали бы н^2 и (1/2)н^2 время, что составляет 100 000 000 и 50 000 000.Мой алгоритм потребовал бы 10 000.Очевидно, что коэффициент 1/2 не имеет значения, поскольку мой результат намного быстрее.А н^2 термин считается доминировать меньшие термины, такие как н и 1/2, что, по сути, делает их незначительными.
Обозначение big-oh выражает семейство функций, поэтому, скажем, «это O (n²)» означает ничего
Это не педантизм, это единственный и правильный способ понять эти вещи.
O (f) = {g | существует x_0 и c, что, для всех x> x_0, g (x) <= f (x) * c}
Теперь предположим, что вы подсчитываете шаги, которые выполняет ваш алгоритм. в худшем случае, делает с точки зрения размера ввода:вызовите эту функцию f.Если f \in O(n²), то вы можете сказать, что ваш алгоритм имеет наихудший случай O(n²) (но также O(n³) или O(2^n)).Бессмысленность констант следует из определения (видите это в?).
Лучший способ понять нотацию Big-O — это получить математическое понимание идеи, лежащей в основе этой нотации.Найдите словарное значение слова «Асимптота».
A line which approaches nearer to some curve than assignable distance, but, though
infinitely extended, would never meet it.
Это определяет максимальное время выполнения (воображаемое, поскольку линия асимптоты пересекает кривую на бесконечности), поэтому все, что вы сделаете, будет меньше этого времени.
Учитывая эту идею, вы, возможно, захотите узнать об обозначениях Big-O, Small-O и омега-обозначениях.
Всегда имейте в виду, что обозначение Big O представляет собой «наихудший» сценарий.В вашем примере первый алгоритм имеет средний случай полного внешнего цикла * полного внутреннего цикла, поэтому, конечно, это n^2.Поскольку во втором случае есть один случай, когда это почти полный внешний цикл * полный внутренний цикл, его необходимо объединить в одну кучу n^2, поскольку это худший случай.Далее ситуация становится только лучше, и ваше среднее значение по сравнению с первой функцией намного ниже.В любом случае, по мере роста n время выполнения ваших функций растет экспоненциально, и это все, что на самом деле говорит вам Big O.Экспоненциальные кривые могут сильно различаться, но в конечном итоге все они одного типа.
