Вопросы с тегом «big-o»

В каждом интервью, в котором я принимал участие, меня опрашивали по математическому анализу сложности, включая нотацию big-O. Насколько актуален анализ big-O для развития в промышленности? Как часто вы действительно используете его, и насколько необходимо иметь отточенное мышление для этой...

Один из моих друзей задал этот вопрос интервью - «Существует постоянный поток чисел, поступающих из некоторого бесконечного списка чисел, из которого вам необходимо поддерживать структуру данных, чтобы возвращать первые 100 старших чисел в любой заданный момент времени. Предположим, что все числа...

Я пытаюсь научить себя, как рассчитать нотацию BigO для произвольной функции. Я нашел эту функцию в учебнике. В книге утверждается, что функция O (n 2 ). Это объясняет, почему это так, но я изо всех сил стараюсь следовать. Интересно, сможет ли кто-нибудь показать мне математику, почему это так? По...

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

Я пытаюсь понять эти классификации и почему они существуют. Правильно ли мое понимание? Если нет, то что? P - полиномиальная сложность, или для некоторого неотрицательного действительного числа , такого как , и т. Д. Если проблема принадлежит P, то существует по крайней мере один алгоритм, который...

Помогите! У меня есть вопрос, где мне нужно проанализировать Big-O алгоритма или некоторый код. Я не уверен точно, что такое Big-O или как оно связано с Big-Theta или другими средствами анализа сложности алгоритма. Я не уверен, относится ли Big-O ко времени выполнения кода или к количеству памяти,...

Я узнал больше о Big O Notation и о том, как рассчитать его на основе написания алгоритма. Я наткнулся на интересный набор «правил» для вычисления нотации алгоритмов Big O и хотел посмотреть, на правильном ли я пути или нет. Big O Обозначение: N function(n) { For(var a = 0; i <= n; i++) { //...

Mergesort является алгоритмом «разделяй и властвуй» и имеет значение O (log n), потому что вход многократно уменьшается вдвое. Но разве это не должно быть O (n), потому что, несмотря на то, что каждый цикл ввода делится пополам на каждый цикл, каждый элемент ввода должен быть повторен для замены в...

Я обновляю свою теорию CS и хочу знать, как определить сложность алгоритма O (log n). В частности, есть ли простой способ определить это? Я знаю, что с O (n) у вас обычно один цикл; O (n ^ 2) - двойная петля; O (n ^ 3) - тройной цикл и т. Д. Как насчет O (log...

Даны два отсортированных массива a , b типа T с размерами n и m . Я ищу алгоритм, который объединяет два массива в новый массив (максимальный размер n + m). Если у вас дешевая операция сравнения, это довольно просто. Просто возьмите из массива с самым низким первым элементом, пока один или оба...

Что такое Big и O в обозначении Big O? Я прочитал определения, и это не говорит о том, что О произносится как «о». Например - я понимаю, что O (n) - это сложность линейного алгоритма, где n может быть числом операций. но что такое O...

У меня есть следующий алгоритм, который находит дубликаты и удаляет их: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] == arr[i - 1]) { numDups++; } } return numDups; } Я пытаюсь найти наихудший случай...

Какой термин я могу использовать для описания чего-либо со сложностью O (N log N)? Например: O (1): постоянная O (log N): логарифмический O (N): линейный O (N log N): ?????? O (N 2 ): квадратичный O (N 3 ): кубический...

Обозначение Big O обеспечивает верхнюю границу для функции, тогда как Big Theta обеспечивает жесткую границу. Однако я считаю, что нотация Big O обычно (и неформально) преподается и используется, когда они действительно означают Big Theta. например, «Быстрая сортировка - это O (N ^ 2)» может...

Закрыто . Этот вопрос основан на мнении . В настоящее время не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос, чтобы ответить на него фактами и цитатами, отредактировав этот пост . Закрыто в прошлом году . Допустим, у меня есть функция, которая сортирует базу данных по...

Я задаю этот вопрос, потому что я запутался в одном аспекте, касающемся обозначения больших О. Я использую книгу Фрэнка Каррано « Структуры данных и абстракции с Java ». В главе «Эффективность алгоритмов» он показывает следующий алгоритм: int sum = 0, i = 1, j = 1 for (i = 1 to n) { for (j = 1 to...

Для любой произвольно двойной рекурсивной функции, как рассчитать время ее выполнения? Например (в псевдокоде): int a(int x){ if (x < = 0) return 1010; else return b(x-1) + a(x-1); } int b(int y){ if (y <= -5) return -2; else return b(a(y-1)); } Или что-то вдоль этих линий. Какие методы можно...

Я программист и только начал читать Алгоритмы. Я не полностью убежден с примечаниями, а именно, Бог О, Большая Омега и Большая Тета. Причина в том, что по определению Большого О он утверждает, что должна быть функция g (x), такая, что она всегда больше или равна f (x). Или f (x) <= cn для всех...

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

Я решаю вопрос об алгоритме, и мой анализ состоит в том, что он будет работать на O (2 ^ sqrt (n)). Насколько большой это? Это соответствует O (2 ^ n)? Это все еще неполиномиальное...