3. Часть 3

Created Friday 10 October 2014

http://habrahabr.ru/post/195996/

Логарифмы


Зелёный — f(n) = n, красный — f(n) = √n, синий — f(n) = log(n)

Практика по логарифмам

http://tutorial.math.lamar.edu/Classes/Alg/LogFunctions.aspx

Рекурсивная сложность

def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)

Логарифмическая сложность

Бинарный поиск


def binarySearch(A, n, value):
if n = 1:
if A[0] = value:
return true
else:
return false
if value < A[n/2]:
return binarySearch(A[0...(n/2 - 1)], n/2 - 1, value)
else if value > A[n/2]:
return binarySearch(A[(n/2 + 1)...n], n/2 - 1, value)
else:
return true

Практическая рекомендация



Backlinks: