Введение в анализ сложности алгоритмов (часть 3)

[jcmvbkbc]

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

binarySearch(*, 2, *) иногда может удивить.

[limon_spb]

Спасибо за переводы!
А можете, пожалуйста, во всех статьях делать ссылки и на прошлые и на следующие, если вас не затруднит (типа оглавления). А то из первой статьи не уйти далее и не понять, сколько их уже переведено :-)

[FeferIvan]

В статье говориться, что для оценки времени работы стоит считать, что в секунду выполняется 10^6 операций. На современнях компьютерах, по крайней мере по моему опыту олимпиадного программирования, это скорее 5*10^7-10^8 операций в секунду. Конкретное число зааисит от сложности операций. Например, целочисленное деление — это относительно долгая операция, а побитовый xor — быстрая.

[Sergery8205]

Хороший перевод. Хочется продолжения темы!