Вопросы по теме 'complexity-theory'
сложность мультимножества, карты и хеш-карты
Я хотел бы знать сложность нотации Big O классов мультимножества STL, карт и хэш-карт, когда:
вставка записей
доступ к записям
получение записей
сравнение записей
66032 просмотров
schedule
30.12.2023
Общие правила упрощения операторов SQL
Я ищу некоторые «правила вывода» (аналогичные установленным правилам работы или логическим правилам), которые я могу использовать для уменьшения сложности или размера SQL-запроса. Есть ли что-то подобное? Какие-нибудь бумаги, какие-нибудь...
17671 просмотров
schedule
08.12.2023
Использование функции Аккермана?
На нашем курсе дискретной математики в моем университете преподаватель показывает своим студентам функции Аккермана и назначает студенту разработать функцию на бумаге.
Помимо эталона оптимизации рекурсии, есть ли у функции Аккермана какое-либо...
8483 просмотров
schedule
23.04.2024
Каковы различия между O (1) и O (2) в алгоритмическом анализе?
Согласно определению большого O f(n) <= C*g(n) (что означает f(n) = O(g(n) ), можно сделать вывод, что:
f(n) <= C
f(n) <= 2C
Я думаю, что между этими двумя нет большой разницы. Что я мог придумать, так это:
f(n) = 1 - 1 / n...
4093 просмотров
schedule
05.12.2023
Сложность рекурсивной факториальной программы
Какова сложность рекурсивной программы для нахождения факториала числа n ? Я подозреваю, что это может быть O(n) .
74707 просмотров
schedule
22.03.2024
Как найти все ссылки на таблицы из функций и процедур Oracle 10G PL/SQL?
Как найти все ссылки на таблицы из функций и процедур Oracle 10G PL/SQL?
Я определенно могу выполнить следующую инструкцию SQL:
select * from dba_source where text like '%tbl_c%'
но мне интересно, как найти все функции, которые вызывают...
20671 просмотров
schedule
02.02.2024
вычисление сложности Лемпеля-Зива (LZ) (также известной как сложность последовательности) двоичной строки
Мне нужно вычислить LZ-сложность двоичной строки. LZ-сложность — это количество разностных подстрок, встречающихся при просмотре потока от начала до конца. Например:
s = 1001111011000010
Разметка в разных подстроках сложности...
5179 просмотров
schedule
29.12.2023
Сложность (вопрос для начинающих)
В чем сложность этих утверждений?
for(int k = 1; k < n; k++)
for(int i = 0; i < n-k; i++){
//O(1) operation here
}
Объяснение приветствуется.
82 просмотров
schedule
22.11.2023
Лучший алгоритм удаления дубликатов в массиве строк
Сегодня в школе учитель попросил нас реализовать алгоритм удаления дубликатов. Это не так сложно, и все придумали следующее решение (псевдокод):
for i from 1 to n - 1
for j from i + 1 to n
if v[i] == v[j] then remove(v, v[j]) //...
19353 просмотров
schedule
05.11.2023
Где я могу использовать технику из алгоритма большинства голосов
Как видно из ответов на алгоритм большинства линейного времени? , можно вычислить большую часть массива элементов в линейном время и log(n) пространство.
Было показано, что каждый, кто видит этот алгоритм, считает, что это крутая техника. Но...
2448 просмотров
schedule
23.01.2024
Является ли log (n) = Ω (n)?
Я считаю, что это не так. Определение таково:
log(n) >= c*n for some n = x, and all n > x
Причина, по которой я думаю, что это не так, заключается в том, что скорость роста c*n = c. Скорость роста log(n) = 1/n. Итак, поскольку n ->...
4673 просмотров
schedule
12.03.2024
Могут ли алгоритмы иметь одинаковую временную сложность в лучшем и худшем случае?
Может ли алгоритм/программа иметь одинаковое время в наихудшем и наилучшем случаях?
Например:
public static int factorial(int number)
{
factorial = 1;
for (i = 1; i <= number; i++)
factorial = factorial * i;
}
Это...
2660 просмотров
schedule
04.04.2024
С++ практическая вычислительная сложность ‹cmath› SQRT()
Какая разница в циклах ЦП (или, по сути, в «скорости») между
x /= y;
а также
#include <cmath>
x = sqrt(y);
РЕДАКТИРОВАТЬ: я знаю, что операции не эквивалентны, я просто произвольно предлагаю x /= y в качестве эталона для...
9991 просмотров
schedule
04.05.2024
Понимание лямбды применительно к Главной теореме
Предположим, у меня есть такой случай, как T (n) = 2T (n/4) + 1. f(n)=1 a=2 и b=4. Таким образом, n^(1/2)>1. Это должен быть случай 1. Однако в случае 1 также есть лямбда, так что f (n) = O (n ^ ((1/2)-лямбда)) для некоторого лямбда> 0. В этом...
1625 просмотров
schedule
24.02.2024
Почему SortedSet‹T›.GetViewBetween не O (log N)?
В .NET 4.0+ класс SortedSet<T> имеет метод с именем GetViewBetween(l, r) , который возвращает представление интерфейса в части дерева, содержащее все значения между двумя указанными. Учитывая, что SortedSet<T> реализовано как...
5501 просмотров
schedule
27.10.2022
сложность сортировки вставками с использованием двусвязного списка?
Сортировка вставками требует вставки элемента в отсортированном порядке путем сдвига элементов уже отсортированного списка при реализации через массив. Если вместо массивов использовать двусвязный список, какова будет временная сложность?...
1943 просмотров
schedule
20.03.2024
Дискретная математика Обозначение Big-O Сложность алгоритма
Я, вероятно, смогу понять часть б, если вы поможете мне сделать часть а. Я весь день смотрю на эту и подобные проблемы, и у меня просто проблемы с пониманием того, что делать с вложенными циклами. Для первого цикла n итераций, для второго n-1, для...
4567 просмотров
schedule
23.10.2022
Как называется эта особая УНВ?
Предположим, у вас есть экземпляр логической выполнимости, где формула дана в CNF. Кроме того, каждое предложение содержит только положительные литералы или отрицательные литералы. Например:
(a || b) && (!a || !c || !d) && (b ||...
393 просмотров
schedule
28.02.2024
Реализация std::string и шаблоны выражений
Кажется, что std::string - поскольку он не использует шаблоны выражений - имеет сложность O (n ^ 2) вместо возможной сложности O (n) для некоторых операций, таких как конкатенация. То же самое с классом std::stringstream, когда вам нужно вставить...
365 просмотров
schedule
20.11.2023
Какова временная сложность многократного удвоения строки?
Рассмотрим следующий фрагмент кода C++:
string s = "a";
for (int i = 0; i < n; i++) {
s = s + s; // Concatenate s with itself.
}
Обычно при анализе временной сложности фрагмента кода мы определяем, сколько работы выполняет внутренний...
575 просмотров
schedule
15.04.2024
