Время работы программы и циклы for (9 сентября 2016)

1. Упражнения на O-шки и асимптотику.
1. O(Θ(O(g)) = ?, O(Θ(Ω(g)) = ?, Θ(Ω(Θ(g)) = ?
2. 1 < loglogN < logN ≈ log2N ≈ log(N²) < log²N = 2^2loglogN < 2^(loglogN)2 < N^ε <
3. √ N  = 2^logN/2 < N < NlogN < Nlog²N < N² = 2^2logN < N^logN = 2^log2N < 2^εN < 2^N < N! < N^N
4. 2ⁿ ≠ Θ(2²ⁿ)
5. (n(2+sin(n)) + arctg(n)) / (√ n  + logn + loglogn) = Θ(√ n )
2. Сколько работает программа
1. 1 секунда = 10⁹ операций = примерно 10⁸ осмысленных действий
2. Сортировка работает за NlogN, массив какой длины можно отсортировать? Все log-и примерно одинаковы.
3. for a=1..n do for b=1..n do → Θ(n²)
4. for a=1..n do for b=a..n do → Θ(n²)
5. for a=1..n do for b=1..ab≤n do → Θ(nlogn)
6. Пять циклов, n⁵/5!
3. Долгие операции
1. cmath: sqrt, sin, cos, atan, ...
2. Вызов функции (если оптимизатор не уберёт его). Пример с рекурсией.
3. Ввод, вывод (scanf/printf, cin/cout)
4. Операции с памятью: new, delete. Работают не за O(1).
5. Доступ к памяти: последовательный и random access. Кеши и оперативная память: 4K, 4M, 4G.
6. Арифметика: сложение/вычитание, умножение, деление
4. Копирование памяти и другие быстрые операции с памятью (регистры AVX по 256 и 512 бит).
5. Примеры
1. Поиск подстроки в строке за квадрат работает быстро.
2. Умножение матриц за n³, for i, for k, for j
6. Задачи
1. Даны N натуральных чисел, найти кол-во различных
1. За O(NlogN) с использованием сортировки
2. За O(N + M), если исходные числа от 1 до M (used[a[i]] = 1)
3. За O(N), если исходные числа произвольные (хеш-таблица)
4. Самая простая реализация хеш-таблицы (List L[M]; a[i] → L[a[i]%M])
2. Решить в натуральных числах уравнение N = x² + y²
1. За O(N)
2. За O(√ N )
3. За O(√ N ) и без извлечения корня (два указателя)
3. Дано N, найти натуральные x, y, z: N = xyz, и величина 2(xy + yz + zx) минимальна
1. За O(N³), O(N²)
2. За O(N^1/3N^1/2) − x ≤ y ≤ z поэтому x ≤ N^1/3, y ≤ N^1/2
3. Более точный анализ: O(N^1/6+1/2) = O(N^2/3)
4. Количество делителей: 10⁹ → 10³; 10¹⁸ → 10⁵