Публикации по теме 'space-complexity'
Что такое нотация Big O с примерами?
Обозначение Big O помогает нам анализировать и сравнивать производительность алгоритмов. В мире алгоритмов «наилучший сценарий» представляет собой наиболее идеальные условия, при которых алгоритм работает с максимальной эффективностью, а «наихудший сценарий» представляет собой наиболее сложные условия, когда алгоритму требуется больше всего времени для выполнения задачи.
Для анализа алгоритмов мы проверяем две сложности: временную и пространственную.
Временная сложность
Временная..
Большое О в программировании
Выполнение программы требует времени и памяти и зависит от скорости обработки компьютера, на котором выполняется программа. Выполнение фрагмента кода на моем компьютере может занять 1 секунду, в то время как тот же код может занять больше или меньше времени на другом компьютере в зависимости от его вычислительной мощности. Это означает, что мы не можем измерить производительность кода на основе времени выполнения, и она не должна зависеть от ресурсов компьютера.
Хороший код имеет два..
Строковые алгоритмы
Краткий обзор 5 строковых алгоритмов: наивный алгоритм Кнута-Морриса-Пратта, алгоритм Бойера-Мура, строковый хэш, суффикс-три.
TL;DR;
Шпаргалка по алгоритмам приведена в конце статьи.
Что первое приходит вам на ум, когда вы слышите слово алгоритмы ? Двоичный поиск, «разделяй и властвуй», алгоритмы DFS, я полагаю. А как насчет строковых алгоритмов?
Давайте поговорим о самых известных алгоритмах String в этой статье.
Что такое алгоритмы String?
Алгоритмы,..
Быстрая сортировка
Рекурсивный алгоритм «разделяй и властвуй».
Быстрая сортировка — это широко используемый алгоритм сортировки, временная сложность которого в лучшем случае составляет O(n log n), а в худшем — O(n²). В худшем случае сортируемый массив уже отсортирован или почти отсортирован.
Быстрая сортировка работает, выбирая элемент массива в качестве «стержня», а затем разделяя массив на два раздела. Один раздел для значений меньше сводного и один раздел для тех, что больше.
Сегодня мы рассмотрим..
Вопросы по теме 'space-complexity'
Как мне изменить структуру моего графика (очень медленная вставка)?
Эта программа, которую я делаю, посвящена социальной сети, а значит, есть пользователи и их профили. Структура профилей UserProfile .
Существуют различные возможные реализации Graph, и я не думаю, что использую лучшую из них. У меня есть...
290 просмотров
schedule
23.07.2023
объединить пространство сортировки
При сортировке слиянием сверху вниз рекурсивные функции вызываются следующим образом:
void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);
mergesort(a, m+1, r);
merge(a, l, m,...
2068 просмотров
schedule
12.04.2022
Будет ли Arrays.sort() увеличивать временную и пространственно-временную сложность?
Существует проблема, связанная с массивом, требование состоит в том, чтобы временная сложность была O (n), а пространственная сложность - O (1).
Если я использую Arrays.sort(arr) и использую цикл for для одного цикла прохода, например:...
50482 просмотров
schedule
13.06.2022
Пространственная сложность для подсчета количества вхождений в отсортированном массиве с использованием двоичного поиска
Мы знаем, что можем подсчитать количество вхождений в отсортированном массиве за время O(LogN) с помощью бинарного поиска [1,2].
[1] http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/
[2] Подсчитайте количество...
211 просмотров
schedule
10.07.2022
вероятностная сложность пространства списка пропусков
Итак, я видел этот вопрос о вероятностном потреблении пространства в списке пропусков:
но я думаю, что спрашивающий не понял, хочет ли он ожидаемого подхода или подхода наихудшего случая.
Поэтому я хотел бы снова поднять этот вопрос в...
360 просмотров
schedule
26.05.2022
Как вы находите пространственную сложность рекурсивных функций, таких как эта?
f (int n){
if (n<=0){
return 1;
}
return f(n-1) + f(n-1);
}
Предположим, мы сделали f(4). Я думал, что это будет O (2 ^ n), поскольку тогда, чтобы найти f (n-1) + f (n-1), нам нужно было бы подтолкнуть f (n-1) = f (3) к...
2203 просмотров
schedule
06.06.2022
Может ли целое число, которое должно содержать значение n, способствовать пространственной сложности?
Если алгоритму требуется целое число, которое может содержать число n (например, для подсчета размера входного массива), это целое число должно иметь порядок log(n) пробела (правильно?).
Если это единственное пространство, масштабируемое с n, то...
53 просмотров
schedule
14.07.2023
Самый длинный возрастающий путь в матричном анализе временной сложности
Я работаю по алгоритму ниже:
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary...
681 просмотров
schedule
12.10.2022
Что такое время и пространственная сложность, чтобы найти максимальную сумму в треугольнике сверху вниз
Алгоритм следующий: какова наилучшая и наихудшая временная и пространственная сложность для нахождения максимальной суммы в треугольнике сверху вниз.
For each ELEMENT in particular ROW and COLUMN
{
If ( ELEMENT is FIRST ELEMENT of ROW)
{...
335 просмотров
schedule
27.05.2022
Какова пространственная сложность сортировки Python?
Какую сложность пространства занимает сортировка Python? Я не могу найти какой-либо окончательной документации по этому вопросу в любом месте
7431 просмотров
schedule
08.06.2024
Временная сложность упрощенной 3-сторонней сортировки разделов
Ниже приведен мой алгоритм, который представляет собой упрощенный алгоритм трехстороннего разделения Дейкстры для общего списка:
static <T extends Comparable> void dutchSort(List<T> list, int left, int right) {
if (left >=...
1448 просмотров
schedule
31.03.2023
Определение сложности времени и пространства для вложенного цикла с одним постоянным коэффициентом
for 1 to n
for j=1 to 3
for i=j to n
count++
Мой ответ: O(n^2)
Пожалуйста, поправьте меня, если я ошибаюсь. Благодарю вас
редактировать: самый внутренний цикл выполняется для O (n), а также самый внешний цикл. А как насчет...
1478 просмотров
schedule
30.09.2023
Сложность пространства-времени в варианте голландского национального флага
Вариант ДНФ выглядит следующим образом:
def dutch_flag_partition(pivot_index , A):
pivot = A[pivot_index]
# First pass: group elements smaller than pivot.
for i in range(len(A)):
# Look for a smaller element.
for j in...
158 просмотров
schedule
08.06.2023
Сложность пространства: инициализация хэш-карты ключами и обновление ее значений отдельно по сравнению с динамическим заполнением пар ключ-значение внутри цикла.
Допустим, у меня есть простая проблема, связанная с возвратом индекса появления всех символов в строке. Я знаю, что вы можете буквально запустить один цикл for и распечатать его, но допустим, мне нужно вернуть его в какой-то структуре данных!...
301 просмотров
schedule
11.04.2023
Пространственная сложность сортировки слиянием в неизменяемом массиве
Пространственная сложность сортировки слиянием составляет O(n), а метод выглядит как void sort(int[] arr) .
Если я создам метод int[] sort(int[] arr) , который не изменяет входной массив, а возвращает новый отсортированный, то какова будет...
110 просмотров
schedule
20.01.2023
Хаскелл; исполнение предложения where
Я анализировал влияние предложений where на производительность программ на Haskell.
В Haskell, Мастерство функционального программирования, Томпсон , глава 20.4 я нашел следующий пример:
exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .....
189 просмотров
schedule
12.05.2023
Какова временная и пространственная сложность задачи 3Sum со следующим алгоритмом?
Была эта проблема, которая требовала вернуть все уникальные триплеты элементов массива, сумма которых равна нулю (перестановка мест двух элементов в триплете не считается уникальной).
Я придумал следующий код:
function threeSum(nums) {...
1366 просмотров
schedule
13.05.2023
Временная и пространственная сложность алгоритма рекурсии файлов
Подходит ли мой анализ времени и пространства для этого алгоритма?
def find_files(suffix, path):
if suffix == '':
return []
# Base condition
if len(os.listdir(path)) == 0:
return []
path_elements = os.listdir(path)
path_files = [file for...
364 просмотров
schedule
28.03.2023
Путаница с временными и пространственными сложностями в коде грубой силы
Недавно я искал решения проблемы, которую нашел на LeetCode. Проблему можно увидеть здесь: https://leetcode.com/articles/best-time-to-buy-and-sell-stock-ii/#
Что касается подхода грубой силы к деталям статьи, я не понимаю, почему временная...
115 просмотров
schedule
28.02.2024
Космическая сложность словаря python
Это вопрос по литкоду
https://leetcode.com/problems/find-the-duplicate-number/
Вот говорят:
Вы не должны изменять массив (предположим, что массив доступен только для чтения). Вы должны использовать только константу, O(1) дополнительное...
277 просмотров
schedule
19.06.2023
