Вопросы с меткой [time-complexity]
Руководство по использованию метки time-complexity отсутствует.
16
вопросов
0
голосов
0
ответов
50
показов
Логарифмическое решение two sum
Решая задачу two sum 2: input array is sorted на leetcode подумал - а нельзя ли совместить binary search и two pointers. В итоге получился код ниже; похоже, что сложность O(logN). Подтвердите или ...
-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):
...
-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)?
0
голосов
1
ответ
110
показов
Какова сложность выполнения запроса со вложенным Length (строки) в LINQ
Есть задача, нужно найти наиболее длинное слово из этого списка, а из наиболее длинных — лексикографически первое слово. В метод передаётся коллекция, нужно вернуть одно слово. В одну операцию, без ...
0
голосов
1
ответ
61
показ
Почему Time Complexity для add() в sorted LinkedList - O(n)?
Столкнулся с сайтом вопрос-ответ. Нашел вот такую цитату:
Какое худшее время работы метода add() для LinkedList?
Ответ
O(N) - будет при добавление элемента в отсортированный список, а также
при ...
0
голосов
0
ответов
24
показа
Существует ли программа, которая считает сложность алгоритмов?
Т.е. я вставляю в нее код, и она возвращает его сложность.
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;
...
5
голосов
1
ответ
231
показ
Асимптотическая сложность операции обхода для вложенных map
Пусть у меня есть такая структура данных :
NavigableMap<Long, NavigableMap<Long, Set<String> map = new TreeMap<>();
Я хочу подсчитать асимптотическую сложность для алгоритма ниже:
...
0
голосов
1
ответ
133
показа
Как расположить элементы в std::list, чтобы поиск элемента по значению происходил бы за время, не большее логарифмического?
Как организовать расположение элементов в std::list, чтобы поиск элемента по значению происходил бы за время, не большее логарифмического в среднем ( amortized O(log(N)) ) ?
Вопрос с собеседования по ...
1
голос
0
ответов
32
показа
Как быстро docker запускает контейнер
Я хочу создавать контейнеры на лету в node js, и возращать ответ. Меня интерисует скорость создания и удаления контейнера и также количесво памяти в это время. Как долго контейнер работает я знаю:).
0
голосов
1
ответ
97
показов
Как узнать, как долго будут вычисляться функция из long.MaxValue шагов?
Час назад я написал такой код, чтобы проверить правильность решенной мною задачи:
static void Main(string[] args)
{
double sum = 0;
for (long i = 1; i < long.MaxValue; i++)
...
0
голосов
1
ответ
578
показов
Является ли данная программа, по нахождению самой частой цифры, эффективной по времени и памяти? И как это определить?
Дан набор из N целых положительных чисел. Необходимо определить, какая цифра чаще всего встречается в десятичной записи чисел этого набора. Если таких цифр несколько, необходимо вывести наибольшую из ...
1
голос
0
ответов
78
показов
Erlang - функция flatten. Время выполнения
Добрый день!
Есть функция которая выглядит вот так:
flatten ([]) -> [];
flatten([H|T]) -> H ++ flatten(T).
Входной лист в функцию может в себе содержать другие листы
К примеру:
flatten([[1,2,3],[...
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) {
...
5
голосов
1
ответ
957
показов
Сложность алгоритма добавления к строке в цикле
Достаточно распространённая gotcha, что
r = ""
for c in s:
r += c
может быть сложностью O(len(s)**2) в Python, но так ли это на самом деле, и если да (или нет), то почему?
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 ...