Вычисление сложности [закрывается]
Высокая вероятность того, что имя FK используется в других таблицах вашей схемы. Пожалуйста, соблюдайте правила именования FK
Источник: Схема именования внешних ключей
3 ответа
Существуют n внешние циклы. В любой точке, k = 3i. Существуют log2(k) внутренние циклы (потому что мы сокращаемся наполовину j на каждом повторении.)
log2(3i) = log3 (3i) / log3(2) = i / (constant)
Таким образом, сложность внутреннего цикла i. Другими словами, эта программа имеет ту же сложность (но не то же самое количество повторений) как
int f4changed(int n)
{
int i, j, count = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < i; j++)
{
count++;
}
}
}
Это O(n2) поскольку Вы уже видели.
i = 1 приводит к 3 повторениям (внутреннего цикла) (3, 1, 0)
i = 2 равняется 8 (5 затем 3)
i = 3 равняется 13 (7 + 5 + 3)
То, что Вы имеете, приближает арифметический ряд, который является O (n2).
Для полноты (и объяснить, почему точное количество повторений не имеет значения), обратитесь к Простому английскому объяснению Большого O (это больше для других читателей, чем Вы, плакат, так как Вы, кажется, знаете то, что произошло).
Сложность Журнала (Голова (3, n)) ~ O (N). Если внутренний цикл был k * = 2, то количество повторений также будет n.
Для вычисления O (~) самый высокий срок полномочий используется, и другими пропускают. Журнал (Голова (3, n)) может быть ограничен как:
Журнал (голова (2, n)) <= журнал (голова (3, n)) <= журнал (голова (4, n))
Теперь журнал (голова (4, n)) = 2*Log (голова (2, n)).
Самый высокий срок полномочий здесь является n (как 2 константа).