尝试用线性时间排序字符串？

Question

我试着用线性时间按字母顺序排列字符串，并考虑使用Pre，我的问题是，在尝试上运行一个预先顺序的横截的时间复杂性是多少？是O(n)吗？

Answer 1

在这种情况下，您必须对度量复杂性的方法稍微小心一点。很多时候，人们假装用基于比较的排序来排序N字符串需要O(N log N)时间，但在最坏的情况下并非如此，除非字符串的长度是有界的。但是，如果字符串是随机的，那么这是预期的时间，因此对于许多用例来说，这并不是一个很好的近似。

如果您想使用长的公共前缀来解释可能的长字符串，那么您可以更改N的含义，以引用输入的总大小，包括所有的字符串。使用这个新定义，您可以在O(N) time中对字符串列表进行排序。

将字符串插入trie或更好的基树(https://en.wikipedia.org/wiki/Radix_tree)，然后执行预顺序遍历是一种方法，是在O(N)时间中工作的，其中N是输入的总大小。

但是做基数排序更快更容易：https://en.wikipedia.org/wiki/Radix_sort --最重要的数字优先变量--在可变长度输入下工作得最好。

Answer 2

在这种情况下，可以应用基数排序在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;
}

Answer 3

不是的。这不是O(n)。它是Omega(k(log(k))n)。没有任何其他限制，正如我从您的问题中了解到的那样，这只是基于比较的排序算法。对长度为k的数组进行排序是在Omega(klog(k))中进行的，并且在没有任何时间连接的情况下进行n次排序将导致Omega(klog(k)n)。您可以在这里阅读更多内容：https://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/

如果你认为k是有界的，因为没有英语的单词超过10^1000000 (这可能比地球上的原子还要大)，那么排序一个有界长度的数组在O(1)中，在n个时间内进行排序将导致O(n)。

你从处理无穷大中得到了很多，但有时你必须偿还.