Время сортировки по основанию

Я готовлюсь к тесту, который у меня есть на этой неделе, и я наткнулся на контрольный вопрос, который спрашивает...

Двадцать миллионов положительных целых чисел в диапазоне 0 . . . 99 999 999 должны быть отсортированы по системе счисления LSD. Сравните производительность при использовании системы счисления 0 . . . 9999 и основание 0 . . . 9. Покажите свою работу.

Я знаю, что время для сортировки по основанию равно тета (d (k + n)); где d = количество цифр, k = размер основания и n = количество записей.

Я понимаю, что десятичная система счисления будет тета (8 (10 + 20 000 000)), верно?

Каким будет основание тысяч? тета(3(1000+20 000 000))?


performance sorting algorithm radix-sort
person user1013032    schedule 17.11.2011    source источник
comment
Считайте свои цифры, это не тысячи.   -  person Daniel Fischer    schedule 18.11.2011
comment
Так должно ли быть тета (2 (10 000 + 20 000 000))? Как будет называться этот корень?   -  person user1013032    schedule 18.11.2011
comment
Мириас, если хочешь похвастаться греческим языком. Или десять тысяч, если хотите, чтобы вас поняли.   -  person Daniel Fischer    schedule 18.11.2011
comment
Итак, я могу сказать, что использование десятитысячной системы счисления примерно в 4 раза быстрее, чем использование десятичной системы счисления?   -  person user1013032    schedule 18.11.2011
comment
Похоже на то (для достаточно больших выборок данных). Однако фактическое отношение может быть другим из-за деталей реализации, местоположения кеша...   -  person Daniel Fischer    schedule 18.11.2011

Ответы (1)


arrow_upward
0
arrow_downward

Вы правы, что время выполнения составляет O (d (n + k)). Это может помочь явно определить связь между d и k. Если вы имеете дело с числами от 0 до числа U, то количество цифр по основанию k в каждом числе будет (logk U) = (log U / log k) . Это означает, что время выполнения более правильно O (log U (n + k)/log k).

В вашем случае k очень мало по сравнению с n, поэтому эта среда выполнения будет иметь for O (n log U/log k).

Ваше утверждение о том, что время выполнения будет (8 (10 + 20 000 000)) и (3 (1 000 + 20 000 000)) немного странное. Помните, что нотация говорит о долгосрочных темпах роста, а не об отдельных значениях, поэтому подставлять значения таким образом не имеет смысла. Тем не менее, ваш основной аргумент верен. Переход от основания 10 к основанию 10000 — это трехкратное увеличение порядка основания, поэтому следует ожидать, что алгоритм будет примерно в три раза быстрее с большим основанием.

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

person templatetypedef    schedule 26.08.2015