Время работы программы и циклы for

Четверг, 18 сентября 2014
ФМЛ 239, Актовый зал

Описание

Упражнения на \(O\)-шки и асимптотику.

Сколько работает программа? Доступ к памяти. Кеширование. Арифметика. Вызов функций. Примеры.

Сколько работают циклы for? Примеры. Решето Эратосфена.

Задачи:

  1. Даны N натуральных чисел, найти кол-во различных (решение сортировкой, хеш-таблицей).

  2. Решить в натуральных числах уравнение N = \(x^2\) + \(y^2\) (решение за \(\sqrt{N}\) сложений/вычитаний).

  3. Дано N, найти натуральные x, y, z: N = xyz, и величина 2(xy + yz + zx) минимальна (решение за \(N^{2/3}\)).

  4. Даны N различных чисел от 1 до N, сколько существует треугольников с такими длинами сторон (решение за \(N^2\)).