algorithm - 大O表示功能

当一个人使用多个函数时，我有一个关于大o符号的问题。
假设我想知道下面的伪代码的时间复杂度是多少：

heap sort array of size n
for i = 1 to n{
  retrieve array[i]
  change value of array[i]
}

我知道使用堆排序是o（n log（n））。由于在数组中检索和改变数据是O（1），所以循环是O（n）的复杂性。
现在我的问题是：这个代码作为一个整体的复杂性是什么？它只是最大的时间复杂度吗？在这种情况下，O（n log（n））是什么？
如果是这样，那么函数的复杂性会是什么样子呢？：

for i = 1 to n{
  // nothing fancy here
}
for y = 1 to n{
  // nothing fancy here either
}

提前谢谢。

最佳答案

Big-O表示法是关于当n（输入大小）接近无穷大时，哪个因素占主导地位因此，如果您有两段代码A和B按顺序执行，那么总体时间行为将是O（A）和O（B）中的较大值。
在您的例子中，如果heapsort是一个O(nlogn)算法，而循环只是一个O(n)算法，那么当n接近无穷大时，nlogn最终会大得多，所以它是唯一重要的术语。所以你的总体时间行为是O(nlogn)。
当然这都是理论在现实世界中，如果要在循环中做一些缓慢的事情（比如I/O），那么在MergeSort比循环慢之前，您的n可能必须变得很大（可能比它所能得到的要大）。

关于algorithm - 大O表示功能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4934349/