Здравствуйте, mgu, Вы писали:
mgu>Здравствуйте, ylp, Вы писали:
ylp>>Я попробую включить тепелата и предположить что в вопросе упоминались алгоритмы сортировки, сравнивающие элементы попарно. Для этих алгоритмов есть математическое доказательство того, что лучше чем в O(NLogN) они работать не могут, это видимо и был предполагаемый ответ на вопрос. А объяснять это вам не стали, потому что целью собеседующего не является вас просвещать.
mgu>А знаете ли вы, что в военное время значение синуса может достигать 4-х? Итак, дано: в войсковую часть привезли из прачечной носки зелёного и чёрного цвета в количестве N штук. Нужно их рассортировать по цвету. Достаём из коробки по 2 штуки и сравниваем попарно. Какова сложность алгоритма?
Я вас поздравляю, вы придумали сортировку подсчетом, которая предполагает разбиение чисел на группы, если число разных чисел известно.
Если "сравнивать попарно". понимать буквально — сравнивать нужно пары чисел из массива между собой, ничего другого делать нельзя (нельзя, например, предполагать что-то о природе эти чисел — например то, что чисел всего 2 и разбивать их на группы).
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
CM>И вместо C1 * O(N) ты получишь C2 * O(N), где C2 < C1 CM>Улавливаешь?
Очень странно, по определение если один алгоритм имеет время работы C1 * N,
а другой C2 * N, где C1 и C2 некоторые константы, то оба эти алгоритма имеют
сложность O(N). Поэтому операция умножения O(N) на константу очень странно выглядит.
Как и попытка сравнения времени работы двух _линейных_ алгоритмов с помощью "O" нотации.
Здесь же она вообще не применима.
Здравствуйте, Zhendos, Вы писали:
Z>Очень странно, по определение если один алгоритм имеет время работы C1 * N, Z>а другой C2 * N, где C1 и C2 некоторые константы, то оба эти алгоритма имеют Z>сложность O(N).
Верно.
Z>Поэтому операция умножения O(N) на константу очень странно выглядит.
ylp>>Спасибо, КО! Вы не заметили, что теперь вы сами себе противоречите? Еще совсем недавно вы говорили про "невозможно реализовать в железе". CM>Врешь. Мой контраргумент с самого начала, цитирую — "бесконечно большие сортирующие сети невозможны"
Ваш конрагрумент на что? Я где-то говорил, что они возможны? Я привел в пример алгоритм сортировки, работающий быстрее чем O(N).
ylp>>Но хорошо хоть что признали, что алгоритм сортировки, сортирующий быстрее, чем O(N) таки существует (хоть и применим не всегда) и согласно вашей же логике, на интервью ответ O(N) без уточнение вопроса был неверным.
CM>См выше про разницу между "сложностью алгоритма" и "скоростью алгоритма".
О, опять философские беседы, люблю такое!
В чем, в чем разница-то?
Вам уже ссылку на определение сложности алгоритма давали, где явно упоминается время выполнения, но пока что что в лоб что по лбу
давайте еще раз, раз вам так нравится:
Time
The resource that is most commonly considered is the time, and one talks of time complexity. When "complexity" is used without being qualified, this generally means time complexity.
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.
Теперь напрягитесь и подумайте, что значит "commonly" и что в случае с сортирующими сетями такое "elementary operation that takes a fixed amount of time to perform". Подсказка — в сортирующих сетях за один интервал времени работают параллельно несколько узлов, а не один.
Здравствуйте, ylp, Вы писали:
ylp>Я где-то говорил, что они возможны?
Как я уже писал, если рассуждать об алгоритмах, которые невозможны практически для общего случая, то твой ответ неверен, а правильный ответ — константное время.
ylp>Я привел в пример алгоритм сортировки, работающий быстрее чем O(N). * ** * subject to terms and conditions
** not really
ylp>Теперь напрягитесь и подумайте, что значит "commonly" и что в случае с сортирующими сетями такое "elementary operation that takes a fixed amount of time to perform". Подсказка — в сортирующих сетях за один интервал времени работают параллельно несколько узлов, а не один.
CM>Как я уже писал, если рассуждать об алгоритмах, которые невозможны практически для общего случая, то твой ответ неверен, а правильный ответ — константное время.
мой ответ на что? Вы мне свои слова не приписываете случайно?
Вы сами привели алгоритм радикс сорта, который за O(N) работает только в случае сортировки чисел фиксированной разрядности. Но это очень нелегко признать, особенно когда с пониманием O() проблема.
ylp>>Теперь напрягитесь и подумайте, что значит "commonly" и что в случае с сортирующими сетями такое "elementary operation that takes a fixed amount of time to perform". Подсказка — в сортирующих сетях за один интервал времени работают параллельно несколько узлов, а не один. CM>Выделил ключевое слово.
Вы пытаетесь казаться умнее, чем есть на самом деле. Не надо так. Я просил подумать, а вы начали что-то выделять. Подумайте еще. Подумайте, наконец, что значит commonly и почему в анализе времени выполнения параллельных алгоритмов никого не волнует сколько операций выполняется паралелльно, а волнует именно время выполнения.
Если вам все еще хочется мне доказать, что при анализе паралельных аллгоритмов важно не время их выполнения, а суммарное число операций, которые они делают, можете не тратить время — я уже все понял, по второму кругу свое невежество демонстрировать не надо
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Чтобы в массиве из миллиона строк каждая строка начиналась на разный символ, размер алфавита должен быть равен миллиону.
CM>Да, начинаешь немного соображать. Именно поэтому я написал "идеальный" и "реальный" случай отдельно. CM>Что-нибудь ответить по существу можешь?
Конечно могу, но начинает уже быть лень. Так уж и быть, объясняю для тупых, в последний раз.
Посколько с "идеальным" случаем вы уже глубоко сидите в луже, давайте разбирать случай реальный. В реальных случаях у нас есть размер алфавита, который будет у нас для определенности m. И есть реальные строки на этом алфавите. Я принципиально не буду уточнять. что такое "реальные строки", пусть будут просто случайные наборы символов.
Число сравнений символов для radix sortа O(N^2) (m считаем константой и не учитываем)
число сравнений символов для quick sortа — O(p*N*LogN), где p — среднее число символов, которые нужно сравнить в рамках одной операци сравнения двух строк, которую делает quicksort, т.е. длина общего префикса двух сравниваемых строк.
будем оценивать p:
у нас есть массив из N строк каждая длины N на алфавите m.
Если каждая строка — это случайная перестановка N элементов алфавита размером m, матожидание размера общего префикса для двух строк равно
(1-m^(-N)) / (m-1) (см https://math.stackexchange.com/questions/1782644/longest-common-prefix-among-n-strings-with-length-k) — т.е. оно околонулевое. Это значит что на случайном наборе строк при попарном их стравненнии в среднем мы обработаем меньше одного символа. Можете убедиться в этом, нагенерировав случайных строк длины 1000 на с m=256 (1 байт) и посравнивав случайные пары из них — у них в среднем почти никогда не будет общего префикса.
Что еще вам оценить, сомневающийся вы наш? Может, провести тот же анализ для длинных строк, являющихся случайными предложениями на человеческом языке? или сами догадаетесь какая там ситуация с матожидаие длины общего префикса?
Здравствуйте, ylp, Вы писали:
ylp>Вы сами привели алгоритм радикс сорта, который за O(N) работает только в случае сортировки чисел фиксированной разрядности.
И quick sort работает за логарифмическое время, опять же, только для чисел фиксированной разрядности. Что касается твоего мега-алгоритма, то он в этом случае не работает вообще.
Ты формулы видел? А понял?
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Вы сами привели алгоритм радикс сорта, который за O(N) работает только в случае сортировки чисел фиксированной разрядности. CM>И quick sort работает за логарифмическое время, опять же, только для чисел фиксированной разрядности.
qiuck sort сортирует не только числа фиксированой разрядности и не работает за логарифмическое время.
он работает в среднем за O(N*Log(N)) для сортировки массива обьектов, сравнение любой пары которых занимает константное время.
>Что касается твоего мега-алгоритма, то он в этом случае не работает вообще.
Какой мой мега-алгоритм?
CM>Ты формулы видел? А понял?
Какие формулы? Вы о чем вообще?
Я понимаю, что вам очень тяжело признавать, что с оценкой числа сравнений символов вы сели в лужу, но жизнь воообще тяжела.
Здравствуйте, ylp, Вы писали:
ylp>Посколько с "идеальным" случаем вы уже глубоко сидите в луже
Хватит булькать.
ylp>Я принципиально не буду уточнять. что такое "реальные строки", пусть будут просто случайные наборы символов.
Случайные строки — это очень хороший случай для сортировки, но пусть.
ylp>Число сравнений символов для radix sortа O(N^2) (m считаем константой и не учитываем)
На самом деле — O(p*N)
Сумеешь сам сравнить с O(p*N*LogN) и сообразить, что меньше, или тебе и в этом нужна помощь?
Здравствуйте, ylp, Вы писали:
ylp>он работает в среднем за O(N*Log(N)) для сортировки массива обьектов, сравнение любой пары которых занимает константное время.
Речь шла о сортировке больших строк и числе сравнений символов, уже забыл?
ylp>Какой мой мега-алгоритм?
Кажется, тебе тоже нужен риталин.
ylp>Какие формулы? Вы о чем вообще?
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>он работает в среднем за O(N*Log(N)) для сортировки массива обьектов, сравнение любой пары которых занимает константное время. CM>Речь шла о сортировке больших строк и числе сравнений символов, уже забыл?
Для сортировки больших строк и числа сравнений символов у нас другай ветка. Я отвечал на конкретную фразу про "логарифмический квиксорт" в этой ветке
ylp>>Какой мой мега-алгоритм?
CM>Кажется, тебе тоже нужен риталин.
не надо свои проблемы другим приписывать
Здравствуйте, ylp, Вы писали:
ylp>Для сортировки больших строк и числа сравнений символов у нас другай ветка. Я отвечал на конкретную фразу про "логарифмический квиксорт" в этой ветке
Значит, внесем эту информацию и в эту ветку. Если сравнивать одинаковые операции, а не метры с килограммами, то квиксорт — и в этом случае все равно медленнее.
ylp>не надо свои проблемы другим приписывать
ylp>>Число сравнений символов для radix sortа O(N^2) (m считаем константой и не учитываем)
CM>На самом деле — O(p*N)
что такое "p" (это что, мое матожидание общего префикса при попарных сравнениях? как оно применимо к радикс сорту, который обрабатывает все символы?) и почему внезапно у нас radix sort работает теперь за O(p*N). Он по вашим же предыдущим выкладкам работал за O(N^2)
в любом случае: логику ваших новых рассуждений (очевидно, что старое сообщение содержит неверную оценку, теперь у нас внезапно radix sort массива N строк длины N работает за O(pN)! ).
CM>Сумеешь сам сравнить с O(p*N*LogN) и сообразить, что меньше, или тебе и в этом нужна помощь?
Мне не нужна ваша помощь, от вас скорее вред. Но чем дальше тем смешнее.
Здравствуйте, ylp, Вы писали:
ylp>как оно применимо к радикс сорту, который обрабатывает все символы?)
Нет, он не обрабатывает все символы. Повторяю еще раз, для самых илпанутых: если в бакете на очередной итерации остается одна строка, то делать обработку глубже уже не нужно.
А одна строка в бакете остается в том случае, если других строк с таким же префиксом нет (sic!). Это на тот случай, если ты сам не сможешь сложить два и два (что очень вероятно ).
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
Мой вопрос про то, что в предыдущей оценке у вас O(N^2) вы предпочли не заметить, ну что ж, ладно
Давайте я на всякий случай повторю ваши слова, чтобы не перепутать:
radix sort сортирует массив из N строк длины N за O(pN).
давайте я еще раз по-другому спрошу: чему в вашем случае равен p? Это явно не константа, т.к. иначе вы ее не стали бы показывать в O(p*N). Это не длина обшего префикса двух случайных строк как в квиксорте, потому что она по моим же оценкам, меньше единицы. Если p зависит от N, какова формула этой зависимости?
Здравствуйте, ylp, Вы писали:
ylp>Мой вопрос про то, что в предыдущей оценке у вас O(N^2) вы предпочли не заметить, ну что ж, ладно
Все зависит от того, какие операции считать. Если тебе так хочется считать посимвольно, то у квиксорта для тех же данных получается O(N^2 * log N)
Ты правда не понимаешь или просто изображаешь полного идиота из каких-то странных соображений?
ylp>давайте я еще раз по-другому спрошу: чему в вашем случае равен p?
То же самое — средняя длина одинакового префикса.
ylp>Это не длина обшего префикса двух случайных строк как в квиксорте, потому что она по моим же оценкам, меньше единицы.
О, вечер становится по настоящему томным. Каким образом ты насчитал меньше единицы для алфавита в 256 символов и 1000 строк?
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Мой вопрос про то, что в предыдущей оценке у вас O(N^2) вы предпочли не заметить, ну что ж, ладно CM>Все зависит от того, какие операции считать. Если тебе так хочется считать посимвольно, то у квиксорта для тех же данных получается O(N^2 * log N)
У квиксорта посимвольно получется O(p*N*logN), потому что квиксорт сравнитвет только общие префиксы строк.
CM>Ты правда не понимаешь или просто изображаешь полного идиота из каких-то странных соображений?
извините, но идиотом во всем этом треде выглядите как раз вы
ylp>>Это не длина обшего префикса двух случайных строк как в квиксорте, потому что она по моим же оценкам, меньше единицы. CM>О, вечер становится по настоящему томным. Каким образом ты насчитал меньше единицы для алфавита в 256 символов и 1000 строк?
Прочитайте внимательно мой ответ. p это матожидание длины общего префискса двух случайно выбраных из N строк. Квиксорт проводит O(N*LogN) сравнений пар строк. И да, сюрприз — для 1000 строк на алфавите из 256 смиволов p будет меньше единицы. Это значит что две случайно выбранные сроки скорее всего вообще не будут иметь общий префикс.
ylp>>давайте я еще раз по-другому спрошу: чему в вашем случае равен p? CM>То же самое — средняя длина одинакового префикса.
Ну ладно, давайте поиграем в эту игру дальше. Чему по вашему равен p? Зависит ли он от размера алфавита и от N?
Здравствуйте, ylp, Вы писали:
ylp>У квиксорта посимвольно получется O(p*N*logN), потому что квиксорт сравнитвет только общие префиксы строк.
Чушь. На самом деле — сравнение заканчивается на первом символе, который отличается. Если сравнивать только общие префиксы, то все строки будут равны (что очевидно для любого, кроме илпа)
И для радикс сорт — тоже. Сюрприииз! (на самом деле нет, я тебя это уже не первый раз повторял. Риталин уже купил?)
ylp>Это значит что две случайно выбранные сроки скорее всего вообще не будут иметь общий префикс.
Очередные чудеса вычислений, интересно где такому учат — в церковно-приходской школе?
На самом деле, компареру нужно будет сравнивать минимум один символ для каждой пары строк, и два и более — еще для какого-то процента пар.
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Это значит что две случайно выбранные сроки скорее всего вообще не будут иметь общий префикс.
CM> CM>Очередные чудеса вычислений, интересно где такому учат — в церковно-приходской школе? CM>На самом деле, компареру нужно будет сравнивать минимум один символ для каждой строки, и два и более — еще для какого-то процента строк.
Понятно, если вы предполчитаете не отвечать на прямо поставленые вопросы о том, что у вас за p в формуле оценки числа сравнений, дальше не о чем разговаривать, слив защитан.
Если вы хотите продолжить дискуссию — дайте свое опрделеление p через N и m. Тогда можно будет сравнить квиксорт с вашим алгоритмом.
Моей следующей просьбой будет его реализация (чтобы наконец увидеть, во что трансформируется MSD radix sort в случае строк длины N),
Если судить по вашим ответам, вы уверены что придумали алгоритм, сортирующий N случайных строк длины N асимтотически быстрее, чем quicksort Я хочу это видеть! (тут дело пахнет нобелевкой, не иначе)
Именно поэтому я написал "идеальный" и "реальный" случай отдельно.
