мимоходом

[avva]

xkcd в своем последнем выпуске впечатлил одновременно изображением куннилингуса и неожиданной метафоричностью alt-текста.

Comments

Roman Bezrukavnikov

[roma.livejournal.com]

а где не напрягаясь посмотреть доказательство оценки n log n? и как ее преодолеть пользуясь внешним сравнением? и как это применить к кунилингусу вписать в отношенческую параллель?

Re: Roman Bezrukavnikov

[avva.livejournal.com]

Где посмотреть, искать лень, поэтому скажу так: если алгоритм сортирует любой порядок за максимум X сравнений, пользуясь только результатами сравнений, то у двух разных порядков последовательность из X результатов сравнений должна быть разной; отсюда 2^X >= n! = O(n^n).

Если алгоритм например знает, что все ключи это числа в промежутке от 1 до 1000, то легко отсортировать их за O(n), пройдясь по ним один раз и только считая для каждого возможного значения, сколько таких попалось. Если вместо от 1 до 1000 разброс значений скажем от 10^-20 до 10^20, то можно последовательно сортировать по цифрам начиная с наименьшего разряда, это называется radix sort и занимает O(n)*20 в данном случае, т.е. опять-таки O(n).

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

Re: Roman Bezrukavnikov

[a-bronx.livejournal.com]

Если алгоритм например знает, что все ключи это числа в промежутке от 1 до 1000

Но чтобы алгоритм знал глобальные свойства входной последовательности, нужно чтобы до него другой алгоритм уже проделал все нужные локальные сравнения. В жизни же все входные последовательности девушки одинаково неповторимы :)

Re: Roman Bezrukavnikov

[roma.livejournal.com]

ага, спасибо, правда оч просто