github twitter email rss
Algorithm analysis
0001 Jun 1
4 minutes read

Algorithm analysis

http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it
http://stackoverflow.com/questions/2626123/how-to-calculate-order-big-o-for-more-complex-algorithms-ie-quicksort

Input
Output
Basic operations
Number of operations
Correct algorithm

Big-Oh notation
Divide conquer algorithm

Randomization

primality testing
graph partitioning

implement

  • Classic Multiplication algorithm
  • Karatsuba Multiplication algorithm
  • Recursive multiplication algorithm

  • Функция роста трудоемкости алгоритма. Принципы построения функции роста.

  • Время выполенния программы и алгоритма. Функция роста. Асимптотическая оценка ф-ии роста.

  • Асимптотическая оценка. Определение О-символики. Ф-ии: Тета, Гамма, Омега, О. Законы О-символики

http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it#3368
http://stackoverflow.com/questions/464078/difference-between-lower-bound-and-tight-bound

http://en.wikipedia.org/wiki/Limit_(mathematics)
http://en.wikipedia.org/wiki/Limit_of_a_function
http://en.wikipedia.org/wiki/Summation
http://en.wikipedia.org/wiki/Stirling's_approximation

https://www.khanacademy.org/math/calculus/limits_topic

http://en.wikipedia.org/wiki/L'H%C3%B4pital's_rule
http://en.wikipedia.org/wiki/L%27H%C3%B4pital%27s_rule
http://mathworld.wolfram.com/LHospitalsRule.html
http://www.youtube.com/watch?v=PdSzruR5OeE

http://en.wikipedia.org/wiki/Mathematical_analysis

Definitions

Asymptotic Behavior

filter of «dropping all factors» and of «keeping the largest growing term»

Time complexity

number of (machine) instructions which a program executes during its running time.

Space complexity

is essentially the number of memory cells which an algorithm needs.

Амортизационный анализ

это оценка среднего времени выполнения одной операции для худшего случая.

[link](http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/amortized-analysis-2004)

Algorithms by problem solving

exact algorithm

approximation algorithm

extracting square roots, solving nonlinear equations, and evaluating definite integrals

Algorithms by execution model

sequential algorithms

parallel algorithms

Классификация алгоритмов по виду функции трудоёмкости

Количественно-зависимые

Количество элементов

Параметрически-зависимые

Значения элементов

Порядково-зависимые

Порядок элементов

Количественно-параметрические

количество, порядок и значения элементов
необходимо проводить анализ для худшего, лучшего и среднего случая

Асимптотический анализ функций

  • Большая тетта (theta) Θ
    (=) asymptotically tight bound
    с1 * g(n) =< f(n) =< c2 * g(n), equal
    bound: upper and lower, tight
    Both Big O and Omega

  • О большое (big-oh) O
    (=<)
    f(n) =< c * g(n), less than or equal
    bound: upper, tightness unknown

  • о малое (small-oh) o
    (<)
    f(n) < c * g(n), less than
    bound: upper, not tight

  • омега большая (big omega) Ω
    (>=)
    с * g(n) =< f(n), greater than or equal
    bound: lower, tightness unknown

  • омега маленькая (small omega) ω
    (>)
    с * g(n) < f(n), greater than
    bound: lower, not tight

Вычисление трудоемкости

  • Следование
    F = F_1 + F_2
  • Ветвление
    анализ вероятности
    F = F_then * p + F_else * (1-p)
  • Цикл
    F = 1 + 3 * N + N * F_тело_цикла


Θ( 1 ) algorithm is a constant-time algorithm
Θ( n ) is linear
Θ( n2 ) is quadratic
Θ( log( n ) ) is logarithmic

Sorting

https://en.wikipedia.org/wiki/Sorting_algorithm

Sorting algorithms properties

comparison sorts

the sorted order algortithms determine is based only on comparisons between the input elements.

Bucket sort

assumes that the input is drawn from a uniform distribution
O(n)

Decision trees

for complete binary tree, T = Ω(N*log(N))

Quicksort

Buddle sort

Mergesort

Heapsort

Introsort

Insertion sort (simple)

Shell sorting

http://www.sorting-algorithms.com/shell-sort
http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%A8%D0%B5%D0%BB%D0%BB%D0%B0
Aho 262

Algorithm analysis

algorithms visualization

http://gauss.ececs.uc.edu/Courses/C321/html/
http://www.csd.uwo.ca/~morey/cs27a02/

http://en.wikipedia.org/wiki/Floor_function
http://en.wikipedia.org/wiki/Worst_case_analysis
http://en.wikipedia.org/wiki/Discrete_Fourier_transform
http://en.wikipedia.org/wiki/Bisection_algorithm
http://en.wikipedia.org/wiki/Logarithmic_time#Logarithmic_time
http://en.wikipedia.org/wiki/Linearithmic#Linearithmic.2Fquasilinear_time
http://en.wikipedia.org/wiki/Powers_of_2
http://en.wikipedia.org/wiki/Natural_logarithm

Search

Amortized analysis

Accounting method

Data structures

Insert, Add, Remove, Read, Write, Search complexity

binary counter

Dictionary

числа {12, 2 ,10, 11, 5, 20, 40, 25, 30, 9, 50 , 1}
8 сегментов
Хеш ф-ия: Метод среднего разряда квадрата числа
Реализовать словарь ( изобразить, реализовать ) открытое хеширование
оценить эффективность O(N)

Dictionary

http://en.wikipedia.org/wiki/Hash_table

– Closed (Inside, Straight hashing)

    Fixed space

Algorithms

Hash function «метод среднего разряда квадрата числа»

возведения числа в квадрат и извлечения из полученного квадрата нескольких средних цифр
Например, если есть число п, состоящее из 5 цифр, то после возведения его в квадрат получим число, состоящее из 9 или 10 цифр. "Средние цифры" — это цифры, стоящие, допустим, на позициях от 4 до 7 (отсчитывая справа).
Их значения, естественно, зависят от числа п. Если В = 100, то для формирования номера сегмента достаточно взять две средние цифры, стоящие, например, на позициях 5 и 6 в квадрате числа.

K - max possible number in set 0, 1 .. K
B - number of buckets
if BC^2 ~ K^2
hash(n) = (n^2/C) % B;

hash("abcd")
    2^7 = 128^1
    n = (128^3)a + (128^2)b + (128^1)c + d;
    hash(n) = (n^2/C) % B;

Matrix

Books

  • «Mathematics for Computer Science - Eric Lehman Tom Leighton» - Sums and Asymptotics (page 447)
  • «Конкретная математика» - Исчисление сумм (стр.39)

Lectures

Articles


Back to posts


comments powered by Disqus