Понимание большого O
Учитывая следующий код, какова сложность 3. и как я представил бы простые алгоритмы со следующими сложностями?
O (n ² + n)
O (n ² + 2n)
O (logn) O (nlogn)
var collection = new[] {1,2,3};
var collection2 = new[] {1,2,3};
//1.
//On
foreach(var i in c1)
{
}
//2.
//On²
foreach(var i in c1)
{
foreach(var j in c1)
{
}
}
//3.
//O(nⁿ⁺ᵒ)?
foreach(var i in c1)
{
foreach(var j in c2)
{
}
}
5 ответов
внешнее foreach выполняется n = | c1 | времена (где |x | является размером c1), в то время как внутреннее foreach выполняется m = | c2 | времена. Это - O (n * m) времена всего.
, как я представил бы простые алгоритмы со следующими сложностями?
- O (n ² + n)
Это совпадает с O (n^2). Что-то, что берет O (n^2) время, выпило бы тост с любым человеком на вечеринке, предположив, что существует всегда точно два человека в тосте, и только один человек делает жарение за один раз.
- O (n ² + 2n)
То же как выше; O (n^2) термин доминирует. Другой пример O (n^2) усилие сажает деревья в квадратном саду длины n, предполагая, что это занимает время для установки каждого дерева, и что, после того как вы сажаете дерево, другие деревья исключены из его близости.
- O (logn)
пример этого нашел бы слово в словаре путем повторного выбора средней точки региона страниц, которые необходимо искать затем. (Другими словами, двоичный поиск.)
- O (nlogn)
Использование вышеупомянутый алгоритм, но теперь необходимо найти каждый слово в словаре.
3 O (n*m) или O (n^2), если эти два набора являются тем же размером.
O (n^2+n) бессмыслен, потому что n меньше, чем n^2. Просто записать O (n^2).
самый достойный вид сравнения алгоритмы, выполненные в O (n*log (n)). Если вы не знаете никого, считаете Википедию.
А двоичный поиск является O (регистрация (n)).
Нет ни O(n²+n), ни O(n^2 + 2n). Оставляя в стороне большинство математических основ сложности алгоритма, нужно хотя бы знать, что он "аимптотический". По мере приближения N к бесконечности, в значении n^2 + n доминирует член n^2, так что асимптотической сложностью n^2 + n.
3 является O(I * J), где I и J - размер входов в c1 и c2.
Сложность 3 равна O (m * n). Нет сложности O (n 2 + n ) или O (n 2 + 2n). Это просто O (n 2 ). Это потому, что n равно o (n 2 ).
Пример O (log (n)) - двоичный поиск.
Пример O (n * log (n)) - сортировка слиянием.