c++ - 性能:找到 arr 中最大值的索引(允许并列)

Question

正如标题，顺便说一句，这只是出于好奇，而不是作业问题。对于CS专业的人来说，这似乎是微不足道的。问题是我想在数组中找到最大值的索引。基本上我有两种方法。

1. 扫描一遍找到最大值，然后扫描两次得到索引 vector

2. 遍历并找到最大值，沿此扫描构造索引数组，如果有更好的则放弃。

现在我应该如何在性能(我想主要是时间复杂度)方面权衡这两种方法？这对我来说很难，因为我什至不知道第二种方法的最坏情况应该是什么!这本身并不是一个难题。但我只想知道如何解决这个问题，或者我应该如何用谷歌搜索这类问题来获得答案。

Answer 1

在复杂性方面:

scan over and find the maximum,
then scan twice to get the vector of indices

第一次扫描是O(n) .
第二次扫描是 O(n) + k插入(k，最大值的数量) vector::push_back具有O(1) 的摊销 复杂性.所以一共O(2 * n + k)可以简化为 O(n)作为k <= n

scan over and find the maximum,
along this scan construct indices array and abandon if a better one is there.

扫描是O(n) .
插入次数计算起来比较复杂。
数量clear (以及清除的元素数量)计算起来也更复杂。 (clear 的复杂度将小于或等于删除的元素数)

但是两者的上限都是n , 所以复杂度小于或等于 O(3 * n) = O(n)但也大于等于 O(n) (扫一扫)原来是O(n)也是。

因此对于这两种方法，复杂度是相同的:O(n) .

对于性能计时，一如既往，您必须进行衡量。