Так что я хочу рассчитать Big O для этого фрагмента кода, но я не уверен, как к нему подойти. Некоторая помощь для начала была бы оценена.Calculate big O
`
for (i = 1 ; i * i < n ; i++){
for (j = 1 ; j < n ; j++)
{
...
}
}
for (i = 1 ; i < n ; i++){
for (j = i % 5 ; i + j < 2000; j++)
{
...
}
`
Хорошо, поэтому мы начинаем с первого внутреннего цикла и видим, что это O(n). Затем i идет от 1 до квадратного корня n, поэтому сложность этого цикла равна O(sqrt(n)). Затем мы умножаем их, чтобы найти сложность для первого вложенного цикла, который равен O(n * sqrt(n)).
Второй внешний цикл имеет сложность n, а внутренний цикл выполняется определенное количество раз (не зависит от n), поэтому общая сложность составляет O(n * sqrt(n) + n).
Заметим тогда, что «O (n * sqrt (n) + n)» совпадает с «O (n * log (n))». –
Big O наихудший сценарий, и в этом случае N^2, потому что у вас есть вложенный цикл внутри первого для цикла.
Второй набор циклов for - это только большой O из N, потому что внутренний цикл будет работать в большинстве случаев в 2000 раз и что в области вещей очень незначительный, особенно когда N огромен.
Это выглядит как домашнее задание. – valverij
Вот массивное сообщение о нотации Big O: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – valverij
Первый внутренний цикл - O (n), внешний цикл O (sqrt (n)), что означает O (n * log n). Второй цикл ... Я должен сказать O (n), так как когда n переходит в бесконечность, внутренний цикл переходит в постоянный, но прошло некоторое время с тех пор, как я взял математику, поэтому возьмите его с солью;) –