Время работы программы и циклы for
Четверг, 18 сентября 2014
ФМЛ 239, Актовый зал
Упражнения на \(O\)-шки и асимптотику.
Сколько работает программа? Доступ к памяти. Кеширование. Арифметика. Вызов функций. Примеры.
Сколько работают циклы for? Примеры. Решето Эратосфена.
Задачи:
Даны N натуральных чисел, найти кол-во различных (решение сортировкой, хеш-таблицей).
Решить в натуральных числах уравнение N = \(x^2\) + \(y^2\) (решение за \(\sqrt{N}\) сложений/вычитаний).
Дано N, найти натуральные x, y, z: N = xyz, и величина 2(xy + yz + zx) минимальна (решение за \(N^{2/3}\)).
Даны N различных чисел от 1 до N, сколько существует треугольников с такими длинами сторон (решение за \(N^2\)).