Публикации по теме 'big-o'
Большое O и эффективность
Что такое Большое О?
Во-первых, позвольте мне начать с того, что означает буква «О» в «Большом О». Заглавная буква «О» означает Порядок программы, а «Большая буква О» — это математические выражения, которые помогают нам, программистам, измерять Временную сложность (эффективность) функции, программы, алгоритма или процедуры, а не в том случае, если они растут или сокращаются.
Что такое временная сложность?
Временная сложность – это количество времени, которое требуется функции,..
Вопросы по теме 'big-o'
Что такое Big-O вложенного цикла, где количество итераций во внутреннем цикле определяется текущей итерацией внешнего цикла?
Какова временная сложность Big-O следующих вложенных циклов:
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
System.out.println("i = " + i + " j = " + j);
}
}
Будет ли это по-прежнему...
67729 просмотров
schedule
10.03.2023
Алгоритм удаления одного элемента из односвязного списка со сложностью O (1)
Я изучаю информатику в Германии. Мой профессор дал возможность подумать над следующим вопросом:
'Дана ссылка на узел в единственном связанном списке (который не является последним узлом). Дайте алгоритм удаления этого элемента из списка, который...
8986 просмотров
schedule
22.03.2023
Асимптотический анализ фрагмента кода
Мне нужно найти большое время работы O следующего фрагмента:
sum =0;
for (int i=1; i<n; i++) {
for (int j=1; j< n/i; j++) {
sum = sum +j;
}
}
Я знаю, что внешний цикл равен O(n), но у меня возникла проблема с анализом...
800 просмотров
schedule
25.05.2023
Время работы в худшем случае (Big O)
У меня есть этот вопрос, и я не знаю, как его решить, потому что я не понимаю его. :(
Вопрос в том:
Программы A и B анализируются, и выясняется, что время выполнения в наихудшем случае не превышает 150 n log n и n 2 соответственно....
2574 просмотров
schedule
23.05.2024
Что такого особенного в нотации Big-O в информатике?
Как нотация Big-O может помочь мне в повседневном программировании на C #? Это просто академическое упражнение?
10399 просмотров
schedule
06.12.2022
Какова фактическая структура данных, используемая при реализации коллекции и их порядок?
В Java используются различные коллекции, такие как хеш-таблица, хэш-набор, вектор, набор деревьев, карта дерева и хэш-карта. Как они реализуются внутри? Какова фактическая структура данных, используемая для этой коллекции? И что такое порядок?...
3984 просмотров
schedule
21.05.2023
Является ли временная сложность пустого алгоритма O (0)?
Итак, учитывая следующую программу:
Является ли временная сложность этой программы O (0)? Другими словами, равно 0 O (0)?
Я думал, что ответ на этот вопрос в отдельном вопросе прольет свет на этот вопрос .
РЕДАКТИРОВАТЬ: здесь много...
18778 просмотров
schedule
11.04.2024
Big O анализ стоимости выполнения сборки мусора
Рассуждая о стоимости времени выполнения в языке со сборщиком мусора, какова стоимость оператора, такого как myList = null; , с точки зрения 'n' (количества элементов в списке)? В качестве аргумента считайте список односвязным списком ссылочных...
939 просмотров
schedule
31.07.2022
сложность перехода от начала к концу и обратно через вектор
Я пытаюсь быть знакомым с оценкой сложности алгоритмов. В общем, я думаю, что это хорошая/элегантная практика, но конкретно мне это нужно, чтобы выразить временную сложность моего кода на C++.
У меня есть небольшое сомнение. Предположим, у меня...
106 просмотров
schedule
25.06.2023
Обозначение и алгоритмы Big O
В настоящее время я изучаю и пытаюсь реализовать некоторые алгоритмы. Я пытаюсь понять нотацию Big O и не могу понять сложность Big O для алгоритма ниже:
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %=...
1882 просмотров
schedule
25.01.2024
Большой O для количества операций для убывающей функции
У меня проблема с циклом, который требует уменьшающегося количества операций при каждом выполнении цикла. Вот код:
for (int i = 1; i < n; i++) {
...code that takes at most 100/i operations to execute...
}
Мне нужно найти большую букву...
747 просмотров
schedule
16.09.2023
Большой вопрос О - Алгоритмический анализ III
У меня следующий вопрос:
Решите рекуррентное соотношение, упростив ответ, используя нотацию Big 'O':
f(0) = 2
f(n) = 6f(n-1)-5, n>0
Я знаю, что это неоднородное рекуррентное соотношение первого порядка, и я пытался ответить на вопрос,...
456 просмотров
schedule
05.06.2022
Исчерпывающий поиск
В настоящее время я работаю над некоторыми изменениями и, в частности, над нотацией Big-O. Я задал аналогичный вопрос (который касался другого алгоритма), но до сих пор не уверен, правильно ли я поступаю или нет.
Алгоритм, на который я смотрю, —...
3807 просмотров
schedule
14.09.2022
Нотация Big Oh (как написать предложение)
У меня был тест про асимптотические обозначения и возник вопрос:
Рассмотрим следующее:
O(o(f(n)) = o(f(n))
Напишите словами смысл утверждения, используя соглашения асимптотической записи.
Является ли утверждение истинным или ложным?...
563 просмотров
schedule
05.03.2023
Большой O и знак равенства, злоупотребление обозначениями
Википедия говорит :
Утверждение «f (x) равно O (g (x))», как определено выше, обычно записывается как f (x) = O (g (x)). Некоторые считают это злоупотреблением обозначениями, поскольку использование знака равенства может ввести в заблуждение,...
630 просмотров
schedule
19.12.2023
Каковы правила для барьера Ω(n log n) для алгоритмов сортировки?
Я написал простую программу, которая сортирует за O(n). Это очень неэффективно с памятью, но это не главное.
Он использует принцип HashMap для сортировки:
public class NLogNBreak {
public static class LinkedListBack {
public...
16474 просмотров
schedule
10.05.2024
Решение рекуррентного соотношения T(n) = √n T(√n) + n
Можно ли решить рекуррентное соотношение
T(n) = √n T(√n) + n
Используя основную теорему? Это не по форме
Т (п) = а Т (п / б) + f (п)
но эта проблема дается в упражнении CLRS, глава 4.
48792 просмотров
schedule
17.07.2022
Насколько сложность сортировки сегментов составляет O (n + k), если мы реализуем сегменты с использованием связанных списков?
Мне любопытно, почему сортировка ведра имеет время выполнения O (n + k), если мы используем корзины, реализованные со связанными списками. Например, предположим, что у нас есть этот ввод:
n = no of element= 8
k = range = 3
array =...
33773 просмотров
schedule
10.08.2023
Как можно построить суффиксное дерево за линейное время?
Чтобы построить дерево суффиксов, в худшем случае, если все буквы строки разные, сложность будет примерно такой
n + (n-1) + (n-2) ... 1 = n*(n+1)/2
что составляет O (n ^ 2).
Однако, согласно http://en.wikipedia.org/wiki/Suffix_tree ,...
12370 просмотров
schedule
29.04.2023
Анализ алгоритмов на временную сложность
Я анализирую алгоритм и просто хочу знать, на правильном ли я пути.
Для этого алгоритма я считаю только умножения в строке, в которой есть ***.
Вот алгоритм:
Итак, я начинаю с самой внутренней строки, я вижу, что там 2 операции (два...
721 просмотров
schedule
02.01.2024
