恆定時間是什麼意思？

Question

我正在研究算法，但我沒有得到關於恆定時間算法。

這是什麼意思和線性時間算法有什麼不同。

感謝，

Answer 1

恆定時間僅表示無論函數的輸入大小如何，成本始終保持不變。

舉個簡單的例子，假設你有一個叫deleteHead功能，這在鏈接的列表中給出一個節點時，返回下一個：

function deleteHead(list) { 
    if(list == null) 
     return null; 
    return list.next; 
} 

不管你把這個列表的大小函數（十個項目，或十億個），它總是隻做一件事使它成爲一個恆定時間算法O（1）。

通過比較的線性算法，將不得不檢查全部鏈表中的N個元素來執行一些計算，這意味着處理更大的列表需要更多的時間。通常，如果不保持結束指針，則將元素添加到鏈表的末尾是線性時間。

Answer 2

當改變爲一個常數時間算法的輸入大小，運行時不會增長。

例如，線性算法，當改變輸入大小時，運行時間增長（線性）。

對於更差的運行時間，比如說指數級，運行時在改變輸入大小時呈指數增長。

例如，參見Wikipedia: Time complexity

Answer 3

對於恆定的時間的算法，執行的時間不依賴於輸入的大小的。對於線性時間，執行時間隨輸入大小線性增加。

Answer 4

這是在大多數基本的計算機科學書籍中找到的。

它只是簡單地描述了算法的輸入長度或對象大小（取決於應用程序）和操作所花費的時間之間的依賴關係。例如。使用列表時，無論列表的大小如何，它都需要執行相同的步驟來在前面/後面添加一個 對象。

需要線性時間來查找列表中的特定項目（在最差和平均的情況下） - 如果您的列表長度是兩倍，則必須查看兩倍的項目才能找到您的項目看起來