Big-O Обозначение алгоритма кода нотации Домашнее задание

Question

for(int i=N; i>0; i=i/2)  
    irrelevant statement;

Меня попросили найти класс сложности, и я не уверен, должен ли я использовать обозначение Big-Omega или Big-O?Но я предполагаю, что это O (N / 2), а затем O (N), если я отбрасываю константы.

for (int i=0; i<N; i++)  
    for (int j = i+1; j<N; j++)  
        irrelevant statement;

Для этого я считаю, что это O (N) * O (N +)1) -> O (N ^ 2 + N) и затем O (N ^ 2) после того, как я уронил N?

Answer 1

Для первого, сколько еще операций будет выполнено, если вы удвоите N?

Answer 2

Первый имеет класс сложности O (log2 (n)), так как при удвоении n он добавляет только еще одну операцию.

Второй - O ((n ^ 2) / 2) или просто O (n ^ 2). Самый простой способ понять это - представить его как форму. У вас есть два цикла for, так что вы знаете, что максимальная сложность равна n ^ 2, но поскольку первое продолжается, второе уменьшается до нуля. Это фактически создает треугольник.

Answer 3

Вы правы насчет второго. Первый - O (logN), а второй - O (N ^ 2). Но есть один , но . То, что вы называете irrelevant statement, может быть очень уместным. Если бы этот оператор был, например, вызовом функции, который, в свою очередь, работает в O (N), то сложности стали бы O (N * logN) и O (N ^ 3) соответственно. Итак, вы правы, если irrelevant statement равно O (1).