【求问】时间复杂度分析的疑问

最近使用Java刷题，有如下疑问

当我们计算时间复杂度的时候，是否需要计算 Java的一些数据结构在调用一些内置方法的开销？

例如：
int arr = new int[]{1,2,4,3,5};
Arrays.sort(arr); //这个位置，我认为应该计算 O(nlogn)的排序开销

当时如果是
for(int i = 0; i < x; i++){
  char ch = string.chatAt(i);//这个chatAt开销是多少我们需要记录吗？
  if(hashset.contains(xxx) == false){ // 这个 HashSet的contains(xx) 开销是多少需要记录吗。。另外还有 HashMap.containsKey(key) 中的containsKey是否需要记录开销呢
//xxx  
}
}

尤其在循环中，如果我们使用了类似 stringA.equals(stringB) 这种，很可能不是O(1)的方法，需要去计算他们的开销吗？

icebane 发表于 2022-9-20 05:56
你说的这些确实都要记录，但也都是o(1)，所以忽略不计。应该是数据结构没怎么学通。建议补习。

Arrays.sort() 不是O(1)

https://stackoverflow.com/questi ... sort-method-in-java

String equal 大部分情况下也不是 O(1)

icebane 发表于 2022-09-20 17:44:05
是O(n), n是String长度没错. 但在整个算法里 这个n是可以忽略不计的, 就是O(n). 这没啥出处. 没有任何一道题, 或者任何一个面试官会去考虑 String.equals()对于算力的

当然是要考虑的，不然很多题里字符串hash，后缀数组这种东西都没有意义了，还有楼上说的kmp也没有意义了

icebane 发表于 2022-9-20 19:44
是O(n), n是String长度没错. 但在整个算法里 这个n是可以忽略不计的, 就是O(n). 这没啥出处. 没有任何一 ...

leetcode里的大部分题目是因为字符串长度有限制，例如少于20个字符，自然不需要考虑String.equal的复杂度，毕竟最多也就是个常数20，这种题目重点也不在字符串上

考字符串的题目里边还是得仔细考虑一下String.equal的复杂度，最简单的例子是如果把String.equal当成O(1)的，KMP算法就没有存在必要了，直接拿S的每个子串去和T判断是否相等就是个线性的字符串匹配算法

当然所有都要记录

你说的这些确实都要记录，但也都是o(1)，所以忽略不计。应该是数据结构没怎么学通。建议补习。

记不清 Java 的新内存分配  memory allocation 的开销如何。
一般认为 amortized 之后是 O(1)，应该是宁可浪费memory，也要节省时间。

时间复杂度，不就是这些各种全部综合考虑的结果么？不然那是在算什么？

Yosaphim 发表于 2022-9-20 17:09
Arrays.sort() 不是O(1)

https://stackoverflow.com/questi ... sort-method-in-java

Arrays.sort() 确实不是O(1), 因为你自己都说答案了, 所以我的意思就不包括这个. 剩下都是O(1). String.equals() 在Leetcode 和 面试里就是O(1), 你非要以算法课的眼光去考虑刷题没有任何意义.

这些要考虑的，凭常识判断就好了，比较容易出错的是PriorityQueue的remove，是O(n)。另外楼上说的String.equals是O(1)的说法，我从来没见到过，包括面试，能否给个出处？

icebane 发表于 2022-09-20 15:42:46
Arrays.sort() 确实不是O(1), 因为你自己都说答案了, 所以我的意思就不包括这个. 剩下都是O(1). String.equals() 在Leetcode 和 面试里就是O(1), 你

String.equals确定是O(1)吗？我第一次见到这种说法，能给个出处不？