Сообщение Re: Когда linear search быстрее hash map от 16.10.2017 7:56
Изменено 16.10.2017 8:15 rg45
Re: Когда linear search быстрее hash map
Здравствуйте, c-smile, Вы писали:
CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от количества итераций, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такое количество итераций, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет это количество итераций, зависит уже от...
CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от количества итераций, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такое количество итераций, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет это количество итераций, зависит уже от...
Re: Когда linear search быстрее hash map
Здравствуйте, c-smile, Вы писали:
CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...
CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.
Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...