Вопросы с меткой [асимптотика]

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

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

Какая асимптотика О большое будет у этого кода

#include <iostream> #include <vector> #include <algorithm> #include <iterator> int main() { std::vector<int> v1{1,2,3,4,5,6,7,8 }; std::vector<int> v2{ ...
Daniel's user avatar
  • 1
-2 голоса
1 ответ
53 показа

Вычислить время выполнения алгоритма и записать результат используя асимптотическую нотацию [закрыт]

Рассчитайте время выполнения алгоритма (псевдокод приведен ниже). Запишите результат асимптотической нотацией. Объясните каждый шаг
Aigul Sarsenbayeva's user avatar
1 голос
1 ответ
99 показов

Где здесь квадратичная сложность?

Дана задача. Нужно реализовать сериализацию и десериализацию связного списка. Сложность алгоритма должна быть не выше квадратичной. Ниже приведен код решения, проверяющие говорят что сложность ...
CunningLobster's user avatar
0 голосов
1 ответ
40 показов

Оценка алгоритма по времени

есть алгоритм: Type ScalarProduct(Type v1[], Type v2[], int n) { int i = 0; Type sum = 0; for (i = 0; i < n; i++) sum += v1[i] * v2[i]; return sum; } высчитывающий ...
tnewplayer232's user avatar
0 голосов
1 ответ
58 показов

Границы подстроки

Можете, пожалуйста, объяснить, что такое границы подстроки. Вот просто есть задача: https://leetcode.com/problems/longest-substring-without-repeating-characters/ и я видел, как кто-то писал, что в ...
randomuser228's user avatar
1 голос
2 ответа
139 показов

Оптимизация кода C++

Очень многие тестирующие системы устанавливают максимальное время работы кода, моя история как раз об этом. Код не проходит на последнем тесте из-за превышения времени работы (дольше 1 сек). Задача ...
Sergey's user avatar
  • 173
0 голосов
1 ответ
494 показа

Асимптотика функции sort(list) в ЯП Python

Видите ли, мне очень важна асимптотика данной функции.
Hemlok Soms's user avatar
2 голоса
1 ответ
181 показ

Алгоритм подсчёта минимума в окне на изображении

Задача очень простая. Дано изображение, массив, пускай int'ов, размером m на n . Мы хотим пройтись по нему окном k на l, и в каждом окне рассчитать минимум (затем этот минимум куда-то записать, но ...
zcorvid's user avatar
  • 2,877
1 голос
1 ответ
63 показа

Алгоритм, становящийся лучше

Здесь вопрос о сложности алгоритмов и можно ли, зная "O" для алгоритма и время для какого-то N, прикинуть время для другого N. По определению O-обозначений оно начинает асимптотически приближаться ...
Mikhailo's user avatar
  • 12.3k
0 голосов
1 ответ
144 показа

Время работы функции в STL

Какое асимптотическое время работы функции q.size() очереди приоритетов?
Максим Фалеев's user avatar
28 голосов
3 ответа
619 показов

Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу: function test(n) { for (i=1; i<100000/n; i++) { dosomething(); } }
Artur Panteleev's user avatar
8 голосов
4 ответа
851 показ

Программно определить вычислительную сложность неизвестного алгоритма JS

Есть функция f : неизвестный алгоритм принимающий на вход одномерный массив . Есть коллекция массивов различной длины data каждый из которых передаю в f. Необходимо написать функцию результатом ...
Vadim Popov's user avatar
7 голосов
1 ответ
9k показов

Что означает O(n^{2}). в описании сложности алгоритма?

Что означает O(n2) в описании сложности алгоритма? Что значит О, что значит n?
Roberto's user avatar
  • 1,173
30 голосов
1 ответ
1k показов

String & StringBuilder

В таких языках как Java и C# для конкатенации большого числа строк принято использовать StringBuilder, чтобы получить линейную асимптотику вместо квадратичной. Однако, JavaScript каким-то образом ...
Qwertiy's user avatar
  • 121k
0 голосов
3 ответа
1k показов

Как оценить время работы алгоритма, зная сложность и значение 'n'?

Как оценить примерное время работы алгоритма, зная сложность и значение 'n'? Например, сложность O(n * log n), а 1 <= n <= 1e5 Использую C++
Andrey Varfolomeev's user avatar
4 голоса
1 ответ
194 показа

Сложность алгоритма, содержащего рандомную операцию

Для всякого ли алгоритма можно оценить сложность при помощи О нотации? Допустим, я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать их буду не по-порядку, а рандомно, в ...
TheSN's user avatar
  • 695
1 голос
2 ответа
839 показов

Сложность алгоритма

Какую сложность имеет алгоритм данной функции ? О(n)? Если да, то можно объяснить почему? public static void merge(ArrayList a, ArrayList b){ if(a.size() == b.size()){ for(int i = 0, j = ...
Mike's user avatar
  • 589
1 голос
3 ответа
3k показов

Варианты оценки производительности алгоритмов

Какие есть варианты оценки производительности алгоритмов на С++??? P.S. Если можно, с простыми примерами.
Дезертир's user avatar
1 голос
2 ответа
1k показов

Время выполнения алгоритма?

Есть алгоритм динамического программирования где нужно найти наибольшую уменьшающуюся подпоследовательность. Алгоритм в данном случае не важен, не могу определится с временем выполнения вот этой ...
koks_rs's user avatar
  • 4,465
1 голос
0 ответов
736 показов

Сложность алгоритмов [дубликат]

Не понимаю, что такое асимптотика сложности алгоритмов, объясните. Например: O(n), O(n^2), O(log n), O(nlog n), o(n), o(n^2), o(log n), o(nlog n).
arcs_host's user avatar
  • 323