Как определить к какому числу в массиве ближе всего данное число

[dimagolov]

DiMA, разве sort, array_unique и т.п. сами по себе не требуют определенного кол-ва операций, которое никогда меньше N не бывает? да и читаемости кода ничуть не лучше того, что я написал

единственное, из чего можно извлечь пользу, это из встроенной в php работы с ключами массивов. но так как у нас на входе произвольный массив, то любое промежуточное преобразование создаст лишние накладные расходы.

 

[fixxxer]

ну как минимум

1) sort() имеет сложность O(n * log n)
2) array_unique внутри выполняет тот же quicksort, а потом линейным проходом удаляет дубликаты

 

[DiMA]

сортировка средствами пхп (готовыми функциями) и в массиве - две больших разницы

 

[fixxxer]

это понятно, но говорить о линейной сложности некорректно полюбому )

O(n log n) в лучшем случае

 

[phprus]

DiMA

В общем случае цикл будет работать всего N/2 раз. И все благодаря сортировке.

Ну и что? Мы же меряем сложность всего алгоритма, а не какого-то из его кусков.
А так-как сортировка работает за N log(N), то меньше этого времени этот алгоритм работать не будет. А в худшем случае твой цикл пройдет все N итераций и тогда сортировка будет только лишним балластом, который только увеличит время выполнения.

А еще можно полностью ЛИНЕЙНО решить задачу

Это далеко не линейное решение. За array_unique скорее всего стоит сортировка те уже N log N набежало, потом еще одна сортировка дает N log N (тут мы константу в сложности только увеличим). Так что этот алгоритм в лучшем случае даст N log N.

Линейный алгоритм привел в этой теме dimagolov

По этому забывать про N не имеет смысла, так как утверждение

для массива из N элементов N операций, меньше то никак не сделаешь

является верным для произвольного массива.

 

[xAntoinex]

Можно было бинарным поиском , используя 2 цикла (один сортирует элементы по неубыванию , второй сам бинарный поиск )

 

[AnrDaemon]

10 лет не срок?