Я читал «Программирование жемчужин», и я действительно запутался в одном из объяснений решения.
Вопрос был:
«Файл, содержащий не более n положительных целых чисел, каждое из которых меньше n, где n = 10 ^ 7. Каждое положительное целое число может появляться не более десяти раз. Как бы вы отсортировали файл?»
Приведенное решение в кн .:
«Если каждое целое число встречается не более десяти раз, то мы можем посчитать его вхождение в четырехбитовую половину байта. Используя решение задачи 5 (ниже), мы можем отсортировать весь файл за один проход с 10 000 000/2 байтов, или в k проходов с 10 000 000 / 2k байтов "
Решение проблемы 5: : алгоритм с двумя проходами сначала сортирует целые числа от 0 до 4 999 999, используя 5 000 000/8 = 625 000 слов памяти, а затем сортирует от 5 000 000 до 9 999 999 за второй проход. Алгоритм k-прохода сортирует не более n неповторяемых натуральных чисел, меньших, чем n, по времени kn и пространству n / k.)
Я не понимаю, как автор подходит к 10 000 000 / 2k места для сортировки. Я имею в виду, основываясь на решении проблемы 5, сначала нам нужно 625 Кбайт пространства для сортировки в первом проходе и дополнительные 1/2 байта на целое число для хранения правильного счета?
Может ли кто-нибудь помочь мне понять это?
Большое спасибо.