Пытается отсортировать строки за линейное время?

Question

Я пытаюсь отсортировать строки в алфавитном порядке по линейному времени и подумал об использовании попыток для этого, у меня вопрос: какова сложность времени при выполнении трансверсального предзаказа на попытки? O (n) ?

Answer 1

Вы должны быть немного осторожны с тем, как вы измеряете сложность в этом случае. Часто люди делают вид, что сортировка N строк с сортировкой на основе сравнения занимает O (N log N) время, но это не совсем так в худшем случае, если только Длина струн ограничена. Это - ожидаемое время, если строки рандомизированы, однако, это не плохое приближение для многих случаев использования.

Если вы хотите учесть возможные длинные строки с длинными общими префиксами, затем вы меняете значение из N , чтобы ссылаться на общий размер ввода, включая все строки. С помощью этого нового определения вы можете отсортировать список строк за O (N) время.

Вставка строк в tr ie или, лучше, радикальное дерево ( https://en.wikipedia.org/wiki/Radix_tree), а затем выполнение обхода предварительного заказа - это один из способов, и да, это работает во время O (N) , где N - общий размер ввода.

Но выполнять сортировку по основанию быстрее и проще: https://en.wikipedia.org/wiki/Radix_sort Наиболее значимый-Di git -Первый вариант лучше всего работает с входами переменной длины.

Answer 2

Нет. это не O (n). это Омега (k (log (k)) n). без каких-либо других ограничений, и, как я понял из вашего вопроса, это тот случай, это всего лишь алгоритм сортировки, основанный на сравнении. Сортировка массива длины k выполняется в Омега (klog (k)), и выполнение этого n раз без каких-либо связей между временами приведет к Омега (klog (k) n). Вы можете прочитать больше здесь: https://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/

Если вы посмотрите на k как ограниченное, потому что нет ENGLI SH слова дольше, чем 10 ^ 1000000 (что, вероятно, больше, чем у атомов на Земле), затем сортируйте массив ограниченной длины в O (1), и выполнение этого n раз приведет к O (n).

Вы получите много от бесконечности, но иногда приходится расплачиваться ...

Answer 3

Radix Sort может применяться в этом случае для сортировки их в O(n). См. Следующий код, реализованный в c ++:

#include<iostream>

using namespace std;

class RadixSort {
    public:

        static char charAt(string s,int n){
            return s[n];
        }

        static void countingSort(string arr[],int n,int index,char lower,char upper){
            int countArray[(upper-lower)+2];
            string tempArray[n];

            for(int i =0; i < sizeof(countArray)/sizeof(countArray[0]); i++)
                countArray[i]=0;

            //increase count for char at index
            for(int i=0;i<n;i++){
                int charIndex = (arr[i].length()-1 < index) ? 0 : (charAt(arr[i],index) - lower+1);
                countArray[charIndex]++;
            }

            //sum up countArray;countArray will hold last index for the char at each strings index
            for(int i=1;i<sizeof(countArray)/sizeof(countArray[0]);i++){
                countArray[i] += countArray[i-1];
            }

            for(int i=n-1;i>=0;i--){
                int charIndex = (arr[i].length()-1 < index) ? 0 : (charAt(arr[i],index) - lower+1);
                tempArray[countArray[charIndex]-1] = arr[i];
                countArray[charIndex]--;
            }

            for(int i=0;i<sizeof(tempArray)/sizeof(tempArray[0]);i++){
                arr[i] = tempArray[i];   
            }
        }

        static void radixSort(string arr[],int n,char lower,char upper){
            int maxIndex = 0;
            for(int i=0;i<n;i++){
                if(arr[i].length()-1 > maxIndex){
                maxIndex = arr[i].length()-1;
                }
            }

            for(int i=maxIndex;i>=0;i--){
                countingSort(arr,n,i,lower,upper);
            }
        }
};


int main(){

    string arr[] = {"a", "aa", "aaa","kinga", "bishoy","computer","az"};
    int n = sizeof(arr)/sizeof(arr[0]);
    RadixSort::radixSort(arr,n,'a','z');
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }

    return 0;
}