You need to enable JavaScript to run this app. 技术问询:Java unique2元素检测算法为何运行时间复杂度为O(nlogn)?
优惠活动
大模型
产品
解决方案
定价
更多

技术问询: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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 15:36:04