技术问询:Java unique2元素检测算法为何运行时间复杂度为O(nlogn)?
unique2 元素检测算法时间复杂度推导
算法实现代码:
public static boolean unique2(int[] data) { int n = data.length; int[] temp = Arrays.copyOf(data, n); Arrays.sort(temp); for (int j = 0; j < n - 1; j++) if (temp[j] == temp[j+1]) return false; return true; }
分步计算各环节时间成本
- 变量赋值操作仅执行常数次,无额外循环成本,可忽略
Arrays.copyOf(data, n)需要逐元素复制长度为n的数组,时间复杂度为O(n)Arrays.sort(temp):Java针对int类型数组的排序采用双轴快速排序实现,平均时间复杂度为O(nlogn),是整个算法的最高成本项- 相邻元素遍历循环最多执行n-1次比对,时间复杂度为O(n)
整体复杂度判定
按照大O表示法的合并规则,仅保留增长量级最高的项,所有线性O(n)的环节都会被更高阶的O(nlogn)覆盖,因此该算法的运行时间复杂度为O(nlogn)
内容的提问来源于stack exchange,提问作者Austin Yan
相关产品推荐
相关产品推荐

