Вопросы с меткой [time-complexity]

Руководство по использованию метки отсутствует.

Фильтрация
Сортировка
Метки
0 голосов
0 ответов
50 показов

Логарифмическое решение two sum

Решая задачу two sum 2: input array is sorted на leetcode подумал - а нельзя ли совместить binary search и two pointers. В итоге получился код ниже; похоже, что сложность O(logN). Подтвердите или ...
Юрыч BRO's user avatar
-4 голоса
1 ответ
44 показа

time complexity рекурсия

Объясните, пожалуйста, почему def f(N): if(N <= 1): return 1 else: x = f(N-1) y = f(N-2) return x+y имеет O(2^n) def f(N): if(N <= 0): return 2 if(N <= 5): ...
russianbillie's user avatar
-1 голос
1 ответ
46 показов

time complexity

Почему if n <= 1: return 0 else: return f(n/2) + 1 по времени O(logN) а if n < 10: return n else: n = n % 10 return f(2*n) по времени O(1)?
russianbillie's user avatar
0 голосов
1 ответ
110 показов

Какова сложность выполнения запроса со вложенным Length (строки) в LINQ

Есть задача, нужно найти наиболее длинное слово из этого списка, а из наиболее длинных — лексикографически первое слово. В метод передаётся коллекция, нужно вернуть одно слово. В одну операцию, без ...
Ilya's user avatar
  • 67
0 голосов
1 ответ
61 показ

Почему Time Complexity для add() в sorted LinkedList - O(n)?

Столкнулся с сайтом вопрос-ответ. Нашел вот такую цитату: Какое худшее время работы метода add() для LinkedList? Ответ O(N) - будет при добавление элемента в отсортированный список, а также при ...
Mark_Daniels's user avatar
0 голосов
0 ответов
24 показа

Существует ли программа, которая считает сложность алгоритмов?

Т.е. я вставляю в нее код, и она возвращает его сложность.
sln's user avatar
  • 611
4 голоса
1 ответ
241 показ

Время работы Math.Pow - const?

Есть 2 функции, находящие n-ное число Фибоначчи. Первое находит через фор-лу Бине O(Log N), второе через метод итераций O(n). static double SQRT5 = Math.Sqrt(5); static double PHI = (SQRT5 + 1) / 2; ...
Runn1ng's user avatar
  • 41
5 голосов
1 ответ
231 показ

Асимптотическая сложность операции обхода для вложенных map

Пусть у меня есть такая структура данных : NavigableMap<Long, NavigableMap<Long, Set<String> map = new TreeMap<>(); Я хочу подсчитать асимптотическую сложность для алгоритма ниже: ...
Artem's user avatar
  • 51
0 голосов
1 ответ
133 показа

Как расположить элементы в std::list, чтобы поиск элемента по значению происходил бы за время, не большее логарифмического?

Как организовать расположение элементов в std::list, чтобы поиск элемента по значению происходил бы за время, не большее логарифмического в среднем ( amortized O(log(N)) ) ? Вопрос с собеседования по ...
Rolando ServerTown's user avatar
1 голос
0 ответов
32 показа

Как быстро docker запускает контейнер

Я хочу создавать контейнеры на лету в node js, и возращать ответ. Меня интерисует скорость создания и удаления контейнера и также количесво памяти в это время. Как долго контейнер работает я знаю:).
ruslan jankurazov's user avatar
0 голосов
1 ответ
97 показов

Как узнать, как долго будут вычисляться функция из long.MaxValue шагов?

Час назад я написал такой код, чтобы проверить правильность решенной мною задачи: static void Main(string[] args) { double sum = 0; for (long i = 1; i < long.MaxValue; i++) ...
Марк Павлович's user avatar
0 голосов
1 ответ
578 показов

Является ли данная программа, по нахождению самой частой цифры, эффективной по времени и памяти? И как это определить?

Дан набор из N целых положительных чисел. Необходимо определить, какая цифра чаще всего встречается в десятичной записи чисел этого набора. Если таких цифр несколько, необходимо вывести наибольшую из ...
Dmitriy Medvedev's user avatar
1 голос
0 ответов
78 показов

Erlang - функция flatten. Время выполнения

Добрый день! Есть функция которая выглядит вот так: flatten ([]) -> []; flatten([H|T]) -> H ++ flatten(T). Входной лист в функцию может в себе содержать другие листы К примеру: flatten([[1,2,3],[...
Sokolik's user avatar
  • 11
0 голосов
1 ответ
80 показов

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

int binsearch(int list[], int searchnum, int left, int right) { int middle; while (left <= right) { middle = (left + right) / 2; if (list[middle] < searchnum) { ...
arman's user avatar
  • 3
5 голосов
1 ответ
957 показов

Сложность алгоритма добавления к строке в цикле

Достаточно распространённая gotcha, что r = "" for c in s: r += c может быть сложностью O(len(s)**2) в Python, но так ли это на самом деле, и если да (или нет), то почему?
Vladimir Gamalyan's user avatar
1 голос
2 ответа
244 показа

Алгоритмы. Сколько раз вызывается print() в функции? Временная сложность циклов с половинным делением i /= 2

Сколько раз вызывается print() в зависимости от параметра n? def f5(n): i = n while i > 0: j = i while j > 0: print(i, j) j = j - 1 i = i ...
tuleviku6's user avatar