Мне нужно сделать ADT, который принимает N несортированных целых чисел и содержит их в отсортированном порядке. Поскольку я обязан сделать это в худшем случае O (N), я думаю использовать радикальную сортировку с сортировкой сегмента. Поэтому я готовлю 10 очередей и ставлю целые числа на основе их 1-ых цифр, т. Е. Если 1-й ди git равен 3, он помещается в 4-ю очередь. Затем я удаляю все элементы из 1-й очереди и помещаю их в соответствующие очереди до 2-х цифр. Сделав это для всех 10 очередей, я переделываю это на 3-й, 4-й ... ди git. Так как это было сделано для максимума ввода di git, все целые числа должны быть отсортированы в очередях, поэтому я просто снимаю их. git, следовательно, время выполнения равно O (KN), где K - максимальное количество цифр на входах, поэтому оно является линейным. Однако, если K стало больше, чем N, мы имеем KN> N ^ 2. В случае, мы можем все еще сказать, что это O (N)?