java - 这种排序算法的时间复杂度是多少？

Question

更好地解释

我有以下问题，我有整数值的源数组，然后我需要通过后缀比较器对源数组进行排序并将其放入排序数组，问题是我想知道构造的时间复杂度是多少后缀数组(排序源数组)

这是排序方法:

Collections.sort(sorted, new SuffixComparator<Integer>(source));

这是 SuffixComparator 类:

public class SuffixComparator<Type extends Comparable<Type>> 
implements java.util.Comparator<Integer> {
List<Type> array1;
List<Type> array2;

/**
 * Constructor with a single array
 */
public SuffixComparator (ArrayList<Type> array) {
array1 = array;
array2 = array;
} 

/**
 * Constructor with two arrays
 */
public SuffixComparator (List<Type> a1, List<Type> a2) {
array1 = a1;
array2 = a2;
}  

/**
 * Constructor with two arrays
 */
public SuffixComparator (ArrayList<Type> a1, ArrayList<Type> a2) {
array1 = a1;
array2 = a2;
}

/**
 * Compare two suffixes 
 * @param offset1 first offset
 * @param offset2 second offset
 */
public int compare (Integer offset1, Integer offset2) {
int result;
if ( array1 == array2 && offset1.equals(offset2) ) {
    result = 0;
} else {
    int n1 = offset1;
    int n2 = offset2;
    while (n1 < array1.size() && 
       n2 < array2.size() && 
       array1.get(n1).equals(array2.get(n2))) {
    ++n1;
    ++n2;
    }
    if (n1 == array1.size()) {
    result = (n2 < array2.size()) ? -1 : 0;
    } else if (n2 == array2.size()) {
    result = 1;
    } else {    // n1 < array1.size && n2 < array2.size
    result = array1.get(n1).compareTo(array2.get(n2)); 
    }
} 
return result;
}

有什么建议吗？

Answer 1

我假设 array1.get() 和 array2.get() 的成本为 O(1)，而忽略计算 println() 的成本 参数，我认为它仅用于调试。 Java 8 的 Collections.sort() 对一般输入执行 O(n log n) 比较。 (更严格的界限可能适用于最初几乎排序的输入。)典型的比较函数成本为 O(1)，但你的似乎成本为 O(k)，其中 k 是 array1.size() 和 array2.size()。因此，基于该比较器的排序行为受到 O(nk log n) 的限制。

可以想象，实际上两者的结合存在更严格的界限，但我没有立即看到它是如何产生的。

但是请注意，在某些情况下，关于 array1.get() 和 array2.get() 成本的假设不成立。特别是，如果一个或两个对象不提供有效的随机访问(例如链表)，并且如果这些对象的大小不受常数限制，则渐近性能会更差。