Что будет большой О этих частях кодов:Big O обозначение для следующего Loops
int sum = 0;
for(int i = 1; i < N; i *= 2)
for(int j =0; j <i; j++)
sum++;
И
int sum = 0;
for(int i = 0; i < N; i *= 2)
for(int j =0; j <i; j++)
sum++;
Моей попытки: По мне, так есть временной сложности, равную O (n^2), так как здесь мы будем умножать n на n, равное n^2. Я прав? Или сделать какую-то ошибку?
Для первой части кода:
первый цикл будет идти от 1 до п с переменной я, как происходит 1, 2, 4, 8, 16 .... п и во второй петли J идет от 0 до I поэтому время сложность будет
O (1 + 2 + 4 + 8 + 16 .... п) = O (2n - 1) = О (п)
и, как для второй части кода
i начинается с 0, оно всегда равно 0, потому что вы умножаете его 2. Его бесконечный цикл.
Это петля внутри цикла i.e вложенная петля. Следовательно, не должно быть n * n = O (n^2)? Если мы не рассматриваем его как вложенный цикл, то он должен быть O (n). Не так ли? –
Я рассматривал его как только вложенный цикл, попробуйте сделать это вручную с помощью небольшого n. –
Так что будет его большим O? –