Описание тега time-complexity
Временная сложность алгоритма определяет количество времени, затрачиваемого алгоритмом на выполнение, в зависимости от размера входных данных проблемы. Временная сложность алгоритма обычно выражается с использованием нотации большого O, которая подавляет мультипликативные константы и члены более низкого порядка.
1
ответ
Почему DFS не проверяет дочерние элементы узла, который был выбран для разработки, на предмет состояния цели
Извините, если моя грамматика далека от совершенства, английский не мой родной язык. Если я правильно понимаю, DFS выполняет целевой тест для узла, только если он был выбран для разработки, а не во время его создания. Мне это кажется странным, потом…
12 май '15 в 20:48
3
ответа
Итеративная сложность времени возведения в квадрат
У меня есть следующая реализация повторного возведения в квадрат: def power(a, b): result = 1 while b > 0: if b % 2 == 1: result = mult(result, a) a = mult(a, a) b = b // 2 return result mult() Метод умножает 2 заданных числа, если, если один име…
28 апр '18 в 10:29
1
ответ
Сложность поиска ключа в словаре
Какова временная сложность этого кода: if 'key' in my_dict: print(my_dict['key']) Я просто хочу убедиться, что условие принимает O(1). Это правильно?
05 дек '13 в 16:51
1
ответ
Большая сложность двух вложенных циклов
Я пытаюсь найти сложность Big-O следующего алгоритма: int i, j; for (i = 0; i < n; i += 5) { for (j = 1; j < n; j *= 3) { // O(1) code here } } n размер массива, переданного в метод. Борьба с этим из-за i += 5 а также j *= 3, Я знаю, что это, …
01 июн '14 в 16:44
3
ответа
Смена монет (Динамическое программирование)
У меня есть вопрос о проблеме замены монет, когда нам нужно не только напечатать количество способов изменить $n с заданными номиналами монет, например, {1,5,10,25}, но также распечатать способы Например, если цель = 50 долларов, а монеты {1,5,10,25…
14 авг '17 в 06:54
1
ответ
Временная сложность детектора краев Canny
В настоящее время я пишу исследовательскую работу о новом алгоритме стеганографии. Я использовал детектор краев Canny в какой-то момент в моем алгоритме. В статье мне нужно написать временную сложность нового подхода, которая, в свою очередь, зависи…
03 июл '13 в 21:14
1
ответ
Как выглядит Big-O Depth-First-Search = O(V+E)?
Я пытаюсь понять, как / почему сложность DFS составляет O(V+E). Вот моя попытка проанализировать сложность псевдокодового итеративного DFS. DFS(G, t) { 1 stack S = new empty Stack of size G.|V| ... O(1) 2 S.push(t) ... O(1) 3 while(S is not Empty) .…
12 ноя '15 в 05:18
3
ответа
Нахождение количества элементов в одном векторе, которые меньше, чем элемент в другом векторе
Скажем, у нас есть пара векторов a <- c(1, 2, 2, 4, 7) b <- c(1, 2, 3, 5, 7) Для каждого элемента b[i] в b Я хочу найти количество элементов в a это меньше чем b[i]или, эквивалентно, я хочу знать ранг b_i в c(b[i], a), Есть несколько наивных с…
08 апр '14 в 16:18
3
ответа
Алгоритм на основе Java, чтобы найти, есть ли в массиве 2 числа, сумма которых равна х
Недавно я наткнулся на интересное утверждение алгоритма Java Given an array int[] arr{} and a number x, find if there are any 2 numbers in the array whose sum is equal to x. Подсказка: решите это тремя способами со следующими сложностями O(n^2), O(n…
25 сен '14 в 11:30
4
ответа
Максимальная сумма несмежных элементов в одномерном массиве
Учитывая массив целых чисел, найдите максимальную сумму несмежных элементов. Например, входы [1, 0, 3, 9, 2,-1] должны возвращать 10 (1 + 9). следует избегать 3,2, так как 9 является соседним для 3,2. максимум в массиве + максимум в несмежных элемен…
05 дек '16 в 18:45
3
ответа
Расчет временной сложности максимальной суммы подпоследовательности
Привет всем, я пытаюсь вычислить временную сложность максимальной суммы подпоследовательности. На самом деле я знаю ответ, который O(n^3), и это следует из функции (n^3 + 3n^2 + 2n)/6 У меня вопрос, как эта функция получается.
11 ноя '13 в 18:13
0
ответов
Как, если внутри цикла for изменить большой O (сложность времени) функции?
Я пытался найти что-то подобное, но безуспешно, если такой вопрос существует, мои извинения. Вернуться к теме. Я начал копаться в записи Big O и прочее. Однако я столкнулся с проблемой, когда я понятия не имею, как выражение if внутри этой конкретно…
22 сен '18 в 16:51
3
ответа
В худшем случае сложность времени для этой глупой сортировки?
Код выглядит так: for (int i = 1; i < N; i++) { if (a[i] < a[i-1]) { swap(i, i-1); i = 0; } } Попробовав несколько вещей, я понял, что наихудший случай - когда входной массив находится в порядке убывания. Тогда выглядит так, что сравнение буде…
10 апр '15 в 22:26
1
ответ
Пространственно-временная сложность "вложенной" рекурсивной функции
В одном из предыдущих вступительных экзаменов в cs возник вопрос: вычислите пространственную и временную сложность функции f1 как функции от n, предположите, что временная сложность malloc (n) равна O(1), а ее пространственная сложность равна На). i…
26 сен '18 в 14:30
0
ответов
Решение ^3 + b^4 = c^3 + d^3 наилучшего времени выполнения
Примечание: этот вопрос отличается от " Напишите все решения для a^3 + b^3 = c^3 + d^3", потому что мне нужна помощь в понимании времени выполнения алгоритма, а не его алгоритма. В "Взломе кодирования", 6-е издание, стр. 69, есть следующий пример: В…
01 июл '17 в 09:56
2
ответа
Сортировка списка строк по заданному порядку
У меня есть множество цветов, которые я хотел бы отсортировать по порядку. Тем не менее, я не хочу сортировать их, используя их "естественный" порядок, а скорее, чтобы держать их в следующем порядке: var order = ['white', 'yellow', 'violet', 'blue',…
17 июн '14 в 22:44
3
ответа
Структура данных с постоянными операциями времени
Мне нужно использовать структуру данных, реализуемую в C++, которая может выполнять основные операции, такие как поиск, вставка и удаление, в постоянное время. Мне, однако, также нужно быть в состоянии найти максимальное значение в постоянное время.…
23 июл '15 в 02:10
1
ответ
Какая временная сложность потребуется для решения RSA Factoring Challenge?
Хотя проблема закончилась давным-давно, мне немного скучно, поэтому я решил попытаться разложить некоторые цифры. Сначала у меня был алгоритм O (n), но затем я решил исследовать большие обозначения O. Очевидно (я могу ошибаться), алгоритмы O (n) и а…
09 дек '17 в 11:41
0
ответов
Collection.deque против списка, Collection.defaultdictionary против набора
Порядок моего алгоритма действительно важен для меня. Интересно, есть ли какая-либо заметная разница между списком и collection.deque (для анализа, оценки и изменения элементов в списке) или между dict и collection.defaultdict(для поиска в наборе)?
15 май '18 в 17:41
1
ответ
Нахождение сложности данного кода
Я борюсь, чтобы найти сложность данного кода. Я думаю, что я борюсь с определением правильной сложности и как на самом деле анализировать сложность. Код для анализа выглядит следующим образом: public void doThings(int[] arr, int start){ boolean foun…
10 ноя '16 в 15:05