Question

Оценить сложность. В каждой задаче дать оценки в терминах oo-малого, OO-большого и \ThetaΘ. for(int i=1; i < n; i++)
for(int j=0; j < n; j+=i)
operations++;

Answer 1

Для оценки сложности данного кода, нужно проанализировать его выполнение шаг за шагом.

1) Первый цикл `for(int i=1; i < n; i++)` выполняется n-1 раз. Каждая итерация этого цикла работает за постоянное время, так как внутри цикла нет операций, которые зависят от i. Таким образом, сложность данной части кода - O(n).

2) Второй цикл `for(int j=0; j < n; j+=i)` выполняется n/i раз для каждой итерации первого цикла. Так как i увеличивается с каждой итерацией первого цикла и может принимать значения от 1 до n-1, то общее количество итераций во втором цикле можно оценить суммой гармонического ряда: n + n/2 + n/3 + ... + n/(n-1). Это асимптотически равно O(n*log(n)).

3) Внутри второго цикла есть операция `operations++`, которая выполняется на каждой итерации цикла. Здесь нужно отметить, что эта операция не зависит от размера данных, а просто увеличивает значение переменной на 1. Таким образом, сложность данной операции - O(1).

Итак, чтобы оценить общую сложность данного кода, мы должны учесть сложность каждой из его частей:

- Первый цикл - O(n)
- Второй цикл - O(n*log(n))
- Операция `operations++` - O(1)

Так как максимальная сложность определяется самой сложной частью кода, то общая сложность данного кода будет O(n*log(n)).