时间戳

首页 > 解决方案 > 对数组进行平方和排序的时间复杂度

java - 对数组进行平方和排序的时间复杂度

问题描述

我有这个代码以排序顺序返回数组的平方，我试图确定它的时间复杂度。我对数据进行一次循环（O(n)），然后使用归并排序（O(n log n)）。我认为这意味着我正在n * n log n工作，所以它很n^2复杂。但是当我检查这个问题的答案时，这个函数的时间复杂度显然只是n log n. 这是为什么？

public int[] sortedSquares(int[] A) {
    for(int i = 0; i < A.length; i++) {
        A[i] = A[i] * A[i];           
    }
    mergeSort(A);
    return A;
}

标签： javaalgorithm

解决方案

您的第一个 for 循环需要O(n)时间复杂度，而合并排序需要O(nlogn)

因此，总体而言，您的时间复杂度将是 T(n) = O(n) + O(nlogn)

由于我们在计算时间复杂度时排除了下界，因此您的整体时间复杂度将为O(nlogn)

推荐阅读