Мне был дан массив целых чисел A[1,2,...n], каждое число в массиве можно описать формулой: n^i + j, где logn >= i >= 1 и n > j >= 0, оба i и j являются целыми числами.
Меня попросили предоставить алгоритм сортировки массива в 2 ситуациях:
даны оба значения i и j, каждое число представлено как (i, j)
и i, и j неизвестны, числа указаны в массиве.Алгоритмы должны запускаться за асимптотическое время, равное меньше чем nlogn
Я попытался представить каждое число в пути i*n+j, а затем использовать радикальную сортировку,но это не время.Я также пытался представить каждое число в виде i*constant+j, но затем я могу получить более одного числа с одной и той же репрезентацией, даже если они разные.