不知道這個算法的運行時間

我被要求寫這個問題的算法：我們給出數組A，我們想知道在U + L = K中是否有任何兩個元素U和L不知道這個算法的運行時間

，我寫我的算法是這樣的：

while(first<last) 
{ 
    if(arr[first]+arr[last]==k) 
    return true 
    else if(arr[first]+arr[last]<k) 
    last=last-1; 
    else 
    first++; 
} 
return false 

}

但問題是，什麼是該算法的運行時間是O（nlogn）？如果是的話爲什麼？如果不是的話，我該如何在O（nlogn）中實現它？

來源

2013-10-20 Hamed Minaee

你100％地肯定ALG求解問題？ – aweis

你正在使用哪種語言？ – hrv

算法的運行時間爲O(N)，因爲在最糟糕的情況下，您最終會遍歷整個數組。

雖然你的算法不能解決問題。例如考慮{9,1,3,4,2}。在這種情況下，如果k將是12，它將返回false。對於你的算法，輸入數組應該先被排序然後傳遞給算法，在最壞的情況下這將需要O(NlogN)。

然而，使用類似HashMap的更快速的解決方案來解決O(N)時間的問題。

來源

2013-10-20 19:59:33 hrv

謝謝你能解釋如何在O（nlogn）中實現它，因爲我被要求在nlogn中實現它嗎？ –

@ user2860721你需要首先使用排序算法對數組進行排序，最壞情況下需要O（NlogN）時間，比如Mergesort（Java中的Arrays.sort使用Mergesort），然後將它提供給算法 – hrv

好極了我完全忘記了對數組進行排序第一個:) –

這裏是蟒蛇的ALG其結果爲假的一個小例子，但在fulfilles在U + L = K列表兩個元素

def testArray(a, k): 
    first = 0 
    last = len(a) - 1 

    while (first < last): 
     print first, last 
     if (a[first] + a[last] == k): 
      return True 
     elif (a[first] + a[last] < k): 
      last=last-1 
     else: 
      first=first+1 
    return False 

a = [3, 1, 5, 3, 6] 
print testArray(a, 6)

來源

2013-10-20 20:09:32 aweis

謝謝你，從你的文章和hrv文章我明白，首先我應該排序數組:) –

不知道這個算法的運行時間

回答

相關問題