Вопросы с меткой [сложность]

Данную метку использовать для всех вопросов связанных с вычислительной сложностью, как функции зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.

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

Big-O рекурсивного создания дерева из плоского списка

Есть метод формирование дерева из плоского списка. Не получается составить формулу рекуррентного соотношения public static IEnumerable<TreeItem<T>> GenerateTree<T, K>( this ...
Aarnihauta's user avatar
  • 2,326
1 голос
1 ответ
49 показов

Какая space complexity у данного алгоритма?

public void ReverseString(char[] s) { char savedElem; for (int i = 0; i < s.Length - i; i++) { savedElem = s[i]; s[i] = s[s.Length - 1 - i]; s[s.Length - 1 - ...
evan's user avatar
  • 79
0 голосов
0 ответов
94 показа

Какая сложность алгоритма?

public int SearchInsert(int[] nums, int target) { int result = 0; for (int i = 0; i < nums.Length; i++) { if (target == nums[i]) result = i; if (nums[i] &...
evan's user avatar
  • 79
1 голос
0 ответов
64 показа

Какая сложность у обращения к элементу списка в Python?

Допустим, есть список: numbers = [1, 2, 3, 4, 5, 6, 7] Я хочу обратиться к списку: print(numbers[4]) Какая сложность у обращения к n-ому элементу списка numbers? O(n) или O(1)
BIT's user avatar
  • 60
3 голоса
4 ответа
332 показа

Есть ли алгоритм со сложностью O(n) для нахождения минимального количества перестановок элементов массива 1, чтобы массив 1 стал равен массиву 2?

Есть 2 массива, элементы которых от 1 до n: current_array = [1, 3, 5, 2, 4, 7, 6] expected_array = [6, 2, 4, 1, 3, 5, 7] Чтобы current_array стал равен expected_array за минимальное количество ...
Finder's user avatar
  • 41
-1 голос
1 ответ
104 показа

Теоретическая оценка вычислительной сложности алгоритма в среднем, лучшем и худшем случаях, оцените асимптотическую сложность

подскажите, пожалуйста, как оценить сложность этого алгоритма. Алгоритм заменяет нули на предыдущее не нулевое значение. a = [3,1,4,0,0,0,0,0,5,0,4,0] b = [] for i in a: b.append(i if i else b[-1])...
Дарья's user avatar
1 голос
1 ответ
132 показа

Как найти время исполнения в наихудшем случае, используя О-большое?

Какое значение выведет следующая функция? Ответ должен быть в форме функции числа n. Найдите время исполнения в наихудшем случае, используя О-большое. Функция на python: def F(n): r = 0 for i ...
TAWER768's user avatar
  • 153
3 голоса
3 ответа
2k показов

Как определять сложность у рекурсивных алгоритмов?

#include <iostream> using namespace std; int no_zeroes(int a, int b) { if (a > b + 1) { return 0; } if (a == 0 || b == 0) { return 1; } return ...
BainkaN17's user avatar
0 голосов
0 ответов
54 показа

Расчет числовых характеристик алгоритма

Написана программа с интерфейсом на Python в ходе отчетной работы. В данной программе реализован алгоритм попиксельного сравнения изображений. Отличия в изображениях выделяются. В алгоритме нет ничего ...
Александр Трифонов's user avatar
7 голосов
2 ответа
904 показа

Почему при оценке сложности алгоритмов используют O-большое, а не o-малое?

Просьба, если в ответе решите использовать высшую математику, переведите сразу на обыденный язык, чтобы все было понятно и не возникло новых вопросов.
Artur Vartanyan's user avatar
0 голосов
1 ответ
971 показ

Поляков - сложная задача на рекурсию двух функций

(№ 2263) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями: F(1) = 1; G(1) = 1; F(n) = F(n–1) – 2·G(n–1), при n >=2 G(n) = F(n–1) + G(n–1) ...
DanchoPancho's user avatar
-1 голос
2 ответа
47 показов

Какая сложность у этого блока кода?

Не могу понять, почему тут сложность O(n^2)? for(i = 0;i<n;i++){ for(j = 0;j<i;j++){ sequence of statements } }
Алексей's user avatar
1 голос
1 ответ
73 показа

O(n/2) - можно ли не учитывать знаменатель?

Слышал такое мнение, что коэффициент при n при описании сложности алгоритма можно не учитывать. Правда ли это? Я считаю, что это мнение ошибочно, поскольку (особенно на больших входных данных) разница ...
smellyshovel's user avatar
  • 5,224
0 голосов
2 ответа
65 показов

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

void MaxValueInArray() { Random rand = new Random(); // O(1) int[] array = new int[rand.Next(0, 10)]; // O(1) int lagerst = 0; //O(1) for (int i = 0; i < array.Length; i++) // ...
Kirill Kulagin's user avatar
0 голосов
0 ответов
63 показа

Как определить сложность алгоритма в коде?

хочу понять какая в данном случае сложность алгоритма if (isSunday(startOfMonth(today)) === true) { for (let i = 0; i < 7; i++) { const element = array[i]; firstWeek.push(...
ArsLoDDD's user avatar
-2 голоса
1 ответ
132 показа

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

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

Помогите определить сложность алгоритма

Код представлен на С++, рекурсивная функция сортировки слиянием, _с - это количество сравнений, m -количество перемещений, intVec - vector void CSort::simpleMerge(intVec& _sortingVec, int64_t&...
Александр Арсеньев's user avatar
0 голосов
0 ответов
135 показов

Какова сложность реализованного алгоритма?

Написал функцию, которая удаляет из массива строки, встречающиеся четное число раз. Мне нужно оценить ее временную сложность. В ней два прохода по всем элементам входного массива, так что вроде как ...
Sergey U's user avatar
0 голосов
1 ответ
78 показов

Big O. Вложенный цикл с if

В общих чертах, ситуация следующая: Я имею такой код: for(i = 0; i < 10; i++) { if(condition) { for(...){ } { else { for(...){ } } } И такой: void ...
Quribe's user avatar
  • 25
1 голос
3 ответа
586 показов

Почему алгоритм работающий за O(n) не всегда быстрее второго за O(n^2)?

Срезали на тесте на этом вопросе. Не могу понять, что не так, я уверен что правильно ответил Вопрос звучит так Первый алгоритм работает за O(n), второй за O(n^2). Выберите верное утверждение 1 - При ...
Дядя Фёдор's user avatar
1 голос
0 ответов
164 показа

Алгоритмы, как изменятся сложность при увеличении данных?

Алгоритм работает за O(n) времени и O(n^2) памяти. Если количество входящих данных увеличить в 2 раза то что получим? В 2 раз увеличится время выполнения и в 4 раза память. Так ли? время - линейно, в ...
Дядя Фёдор's user avatar
0 голосов
1 ответ
451 показ

Какая асимптотическая скорость самая медленная?

Какая асимптотическая скорость самая медленная? 1 - О(3^n) 2 - О(n^3) 3 - О(n^2 log_2n) 4 - О(2^n) Я ответил неправильно О(3^n), только я не понимаю, почему я не прав? Нас учили, что нужно исключить ...
Дядя Фёдор's user avatar
1 голос
1 ответ
445 показов

Как оценить сложность алгоритма не зная кол-во итераций

Есть алгоритм cin >> e; int n = 1; double S = 0, i = 0; do { S += i; i = 1 / (pow(3, n) - 1); n++; } while (i >= e); cout << "Сумма S = " << S; он же на ...
ryder93's user avatar
  • 11
0 голосов
0 ответов
77 показов

Как рассчитать сложность алгоритма?

мне нужно рассчитать сложность данного алгоритма: for(int i = 0; i < n; i+=2) for (int j = 0; j < i; j++) operations++; У меня получилось примерно это, но я не уверен в ...
leshaz's user avatar
  • 11
2 голоса
2 ответа
236 показов

Как избежать сложности O(N*M)?

Есть список List<User> users объектов следующего класса: public class User { Set<String> groups; } И имеется список Set<String> targetGroups. Необходимо найти всех пользователей,...
Zhenyria's user avatar
  • 2,141
0 голосов
1 ответ
73 показа

Как распределить маршруты по дням в месяце?

нужна помощь с распределением маршрутов по дням месяца. Ситуация такая. Есть к примеру 3 зоны, в каждой зоне есть маршруты(не всегда равное количество). Задача распределить маршруты по рабочим дням в ...
Stepback's user avatar
1 голос
1 ответ
224 показа

Уменьшение сложности алгоритма

Всем привет! Прошу помощи в понимании как правильно оценить и, самое главное, уменьшить сложность алгоритма. Проблема - тормозит анимация интерфейса на React при обращении к базе на одном из легаси ...
Sergei Tereshkov's user avatar
6 голосов
2 ответа
174 показа

Что означает именно такой big O: O(|E|)

Проходил тест по BIG O и попался такой вопрос: Incidence Matrix -> Матрица инцидентности Graph Operations: Incidence Matrix Query O(|V| + |E|) O(1) O(|E|) -> правильный ответ O(|V|) O(|V|²) O(...
Randall's user avatar
  • 7,054
-3 голоса
1 ответ
543 показа

Какая временная сложность counter и sorted?

#1 from collections import Counter company = {'A': 3.75, 'B': 44.2, 'C': 12.4, 'D': 44.5, 'E': 10.1} count = Counter(company) print(count.most_common(3)) #2 company = {'A': 3.75, 'B': 44.2, 'C': 12....
Валерия's user avatar
2 голоса
1 ответ
270 показов

Пространственная сложность рекурсивного алгоритма обхода дерева

Есть задача - проверить, что в бинарном дереве все узлы имеют одинаковое значение. И есть эталонное решение при помощи рекурсии: class Solution { public bool IsUnivalTree(TreeNode root) { ...
A K's user avatar
  • 28.7k
1 голос
1 ответ
470 показов

Как правильно сформулировать равенство O(2n) = O(n)

Существует алгоритм, который решает задачу за 2n шагов, где 2n -- размер массива входных данных. Мне нужно в конце доказательства написать, что алгоритм имеет сложность O(n). Как правильно это ...
timovadia's user avatar
0 голосов
1 ответ
194 показа

Однопроходный алгоритм одной задачи

Как решить данную задачу за один проход или не более чем за O(n)? Может быть с созданием предварительно какой-то структуры? Задача. Дана последовательность натуральных чисел от 1 до N (N заранее ...
timovadia's user avatar
1 голос
1 ответ
50 показов

Аналитически оценить временную ассимптотическую сложность функции

Нужно аналитически вычислить временную асимптотическую сложность алгоритма. Пытался, но не понимаю что делать с условиями, подключать теорию вероятностей?
Егор's user avatar
5 голосов
1 ответ
259 показов

Как считать сложность алгоритма?

Что я имею ввиду когда говорю о подсчете сложности алгоритма? К примеру вы написали какую-то функцию, которая: сортирует два массива, проходится по ним циклом составляя на их основе некий новый массив ...
Andrej Levkovitch's user avatar
-2 голоса
1 ответ
263 показа

Определить сложность алгоритма

сомневаюсь в правильности определения сложности алгоритма, подскажите каковой она является: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading....
Женя Ермолаев's user avatar
1 голос
1 ответ
452 показа

Посчитать сложность алгоритма C#

Как правильно посчитать сложность алгоритма? Смотрю все примеры, которые есть на stackoverflow и все равно никак не пойму. Сам алгоритм С#: class Program { static int sum(int mas_kol) { ...
Artem L.'s user avatar
2 голоса
1 ответ
83 показа

Оценка сложности алгоритма

Предположим, у меня есть дерево. Передо мной стоит задача: найти самый глубокий лист, учитывая его корень. Вот псевдокод: heightFunc(elem) height = 1; for all children c in elem: height = ...
Elizaveta's user avatar
  • 408
2 голоса
1 ответ
38 показов

Где можно узнать производительность AA-tree?

Конкретно о производительности алгоритма, (средний, худший случай). Где можно узнать это?
Rumeone's user avatar
  • 71
5 голосов
3 ответа
522 показа

Как перевернуть дек или список за O(1)?

Дали задание перевернуть список или дек за O(1). Точнее, сказано было, что надо перевернуть, не переворачивая буквально... То есть Reverse, reversed и [::-1] нельзя, потому что они все O(n). Как быть?
braflovsky's user avatar
5 голосов
2 ответа
251 показ

Сколько нужно шагов, чтобы упорядочить буквы в строке O(nlogn)

В строке содержатся только буквы X, Y или Z. Нужно упорядочить их по алфавиту в минимальное количество шагов. За один шаг можно менять местами две любые буквы. Например, упорядочить строку ZYXZYX ...
braflovsky's user avatar
2 голоса
1 ответ
138 показов

Алгоритмы, оценка сложности функции

Покажите, что для произвольной константы c > 0 функция g(n) = 1 + c + c^2 + ... + c^n есть (а) Θ(1), если с < 1; (b) Θ(n), если c = 1; (c) Θ(c^n), если c > 1. Другими словами, в сумме ...
lunary's user avatar
  • 35
2 голоса
1 ответ
229 показов

Как определить сложность алгоритма сортировки?

Имеется алгоритм сортировки: def search(a): if len(a) < 2: return a pivot = a[0] left = [int(i) for i in a[1:] if i < pivot] right = [int(i) for i in a[1:] if i > ...
Maksim's user avatar
  • 217
0 голосов
0 ответов
203 показа

Сумма, делящаяся на три C++ [дубликат]

Условие: (После - моё решение, вопрос и комментарии) Необходимо найти самый большой непрерывный фрагмент в массиве a1, a2... aN, сумма элементов которого делится на 3. Входные данные В первой строке ...
user avatar
0 голосов
1 ответ
662 показа

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

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

Как составить программу в соответствии с временной сложностью алгоритма O(2*n) и O(n)?

#include <iostream> #include <conio.h> #include <locale> #include <cstdlib> //для генерации рандомных чисел #define SIZE 28 using namespace std; int main() { setlocale(...
Muriam's user avatar
  • 371
0 голосов
1 ответ
64 показа

Как описать сложность расчета глубины графика DFS?

Как описать сложность расчета глубины графика DFS? Можно реализация сложность алгоритма?
Leskhan Muratuly's user avatar
3 голоса
1 ответ
222 показа

Задача на сумму матриц

Допустим у меня есть некая матрица A размера q×q. Мне нужно найти сумму A + A2 + ... + An, при этом сложность вычисления этой суммы должна быть O(q3log(n)). Как это сделать?
Sam's user avatar
  • 57
1 голос
2 ответа
346 показов

Я создал идеальный алгоритм сортировки расческой?

Код: public static void raschestkaSort(int[] a){ for(int d = a.length - 2; d >= 0; d--){ for(int i = 0; i <= (a.length - 2) - d; i++){ if(a[i] > a[i + d + 1]){ ...
Miron's user avatar
  • 3,027
0 голосов
1 ответ
110 показов

Как правильно определить скорость роста времени работы алгоритма?

Вот, дают задание такое, к которому есть такая формула: Вроде бы сказано, что нужно взять член с самой большой степенью, и тогда будет O(n^3), но! Если просто включить логику немного и подумать, то ...
megorit's user avatar
  • 1,945
0 голосов
1 ответ
263 показа

Двусвязный список на низком уровне: вставка элемента за константное время

На уровне аллокатора памяти требуется реализовать двусвязный список. Сперва выделяется память уже готовым аллокатором - именно она в дальнейшем используется для списка. В самое начало кладутся ...
Marionette's user avatar