Время работы программы и циклы 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(N2) < log2N = 22loglogN < 2(loglogN)2 < Nε < √ N  = 2logN/2 < N < NlogN < Nlog2N < N2 = 22logN < NlogN = 2log2N < 2εN < 2N < N! < NN
    3. 2n ≠ Θ(22n)
    4. (n(2+sin(n)) + arctg(n)) / (√ N  + logn + loglogn) = Θ(√ N );
  3. Сколько работает программа
    1. 1 секунда = 109 операций = примерно 108 осмысленных действий
    2. Копирование памяти и другие операции с памятью (регистры по 256 и 512 бит)
    3. Арифметика: сложение/вычитание, умножение, деление, извлечение корня, тригонометрия.
    4. Доступ к памяти: последовательный и random access. Кеши и оперативная память: 4K, 4M, 4G.
    5. Вызов функции. inplace функции.
    6. Примеры:
      1. [память] Поиск подстроки в строке за квадрат.
      2. [кеш] Умножение матриц (кеширование, доступ к памяти).
      3. [арифметика] Вычисление n-го числа Фибоначчи по модулю 109+7.
      4. [арифметика] Произведение длинных чисел за квадрат.
  4. Сколько работают циклы for
    1. for a=1..n do for b=1..n do → Θ(n2)
    2. for a=1..n do for b=a..n do → Θ(n2)
    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 = x2 + y2
      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(N3)
      2. За O(N2)
      3. За O(N1/3N1/2) − x ≤ y ≤ z поэтому x ≤ N1/3, y ≤ N1/2
      4. Более точный анализ: O(N1/6+1/2) = O(N2/3)
      5. Оценка суммы интегралом снизу и сверху.
      6. За O(N1/2 + Neps) − нашли все делители числа N, перебираем x, y, z, как делители числа
      7. Количество делителей: 109 → 103; 1018 → 105


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