我正在阅读:https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/。
我认为在方法2(哈希)的时间复杂度计算中存在错误,他们声称它的时间复杂度是O(n),但我坚持认为它是O(n)摊销。
算法如下:
1. 初始化一个空哈希表s。 2. 对于A[]中的每个元素A[i]执行以下操作: 2.1 如果s[x-A[i]]已经设置,则打印出对(A[i], x-A[i]) 2.2 将A[i]插入哈希表s中。
步骤1需要O(1)时间。步骤2需要O(n)次迭代,对于每一次迭代我们都需要O(1)(2.1和2.2)的摊销时间,因此总的时间复杂度为O(n)摊销。
我认为在方法2(哈希)的时间复杂度计算中存在错误,他们声称它的时间复杂度是O(n),但我坚持认为它是O(n)摊销。
算法如下:
1. 初始化一个空哈希表s。 2. 对于A[]中的每个元素A[i]执行以下操作: 2.1 如果s[x-A[i]]已经设置,则打印出对(A[i], x-A[i]) 2.2 将A[i]插入哈希表s中。
步骤1需要O(1)时间。步骤2需要O(n)次迭代,对于每一次迭代我们都需要O(1)(2.1和2.2)的摊销时间,因此总的时间复杂度为O(n)摊销。