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

1. Соцопрос
1. Математика (простые числа, комплексные числа, Гаусс, ортоганализация Грамма-Шмидта)
2. Языки программирования (C++, Java, Python, Haskell или любой друг функ.язык, ASM)
2. Упражения на O-шки и асимптотику.
1. O(Θ(O(g)) = ?, O(Θ(Ω(g)) = ?, Θ(Ω(Θ(g)) = ?
2. 1 < loglogN < logN ≈ log2N ≈ log(N²) < log²N = 2^2loglogN < 2^(loglogN)2 < N^ε < √ N  = 2^logN/2 < N < NlogN < Nlog²N < N² = 2^2logN < N^logN = 2^log2N < 2^εN < 2^N < N! < N^N
3. 2ⁿ ≠ Θ(2²ⁿ)
4. (n(2+sin(n)) + arctg(n)) / (√ N  + logn + loglogn) = Θ(√ N );
3. Сколько работает программа
1. 1 секунда = 10⁹ операций = примерно 10⁸ осмысленных действий
2. Копирование памяти и другие операции с памятью (регистры по 256 и 512 бит)
3. Арифметика: сложение/вычитание, умножение, деление, извлечение корня, тригонометрия.
4. Доступ к памяти: последовательный и random access. Кеши и оперативная память: 4K, 4M, 4G.
5. Вызов функции. inplace функции.
6. Примеры:
1. [память] Поиск подстроки в строке за квадрат.
2. [кеш] Умножение матриц (кеширование, доступ к памяти).
3. [арифметика] Вычисление n-го числа Фибоначчи по модулю 10⁹+7.
4. [арифметика] Произведение длинных чисел за квадрат.
4. Сколько работают циклы for
1. for a=1..n do for b=1..n do → Θ(n²)
2. for a=1..n do for b=a..n do → Θ(n²)
3. for a=1..n do for b=1..ab≤n do → Θ(nlogn)
4. Решето Эратосфена. Доказательство времени работы O(nlogn)
5. Задачи
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 ) и без извлечения корня (два указателя)
4. Как еще оптимизировать: убрать все умножения (-20%), минимизировать количество сложений/вычитаний/сравнений (еще -10%)
3. Дано N, найти натуральные x, y, z: N = xyz, и величина 2(xy + yz + zx) минимальна
1. За O(N³)
2. За O(N²)
3. За O(N^1/3N^1/2) − x ≤ y ≤ z поэтому x ≤ N^1/3, y ≤ N^1/2
4. Более точный анализ: O(N^1/6+1/2) = O(N^2/3)
5. Оценка суммы интегралом снизу и сверху.
6. За O(N^1/2 + N^eps) − нашли все делители числа N, перебираем x, y, z, как делители числа
7. Количество делителей: 10⁹ → 10³; 10¹⁸ → 10⁵



6. Упражения на дом
1. Доказать, ∀ε > 0 : D(n) = O(n^ε), где D(n) − количество делителей числа
2. Доказать, что последний алгоритм решения задачи "холодильник" работает за O(N^1/2).