爲什麼一個循環的執行時間是不成正比的循環

Question

我寫了這個「壞」作用的大小（volontary慢）來構建載體和測試執行時間：

f <- function(n){ 
    vec <- c() 
    for (i in 1:n) { 
    vec <- c(vec, i) 
    } 
} 

我認爲如果我將循環的大小乘以10，則函數的執行時間將按比例增加。但是，我們可以看到，執行時間是不是在所有的比例，甚至十分優越：

> system.time(f(1e+04)) 
utilisateur  système  écoulé 
0.14  0.00  0.14 
> system.time(f(1e+05)) 
utilisateur  système  écoulé 
13.35  0.00  13.49 
> system.time(f(1e+06)) 

Timing stopped at: 1322.7 0.29 1338.59 

也許這是一個基本的計算概念，但我不知道爲什麼這個循環的執行時間（但我認爲這是同樣的事情一般的循環）與循環的大小不成正比？

謝謝

Answer 1

這是由增量增長對象造成的。每次增加對象的大小（vec <- c(vec, i)）時，都必須在內存中爲新對象分配一個新位置。這涉及分配一組新內存，並將舊對象和新部分複製到新分配的空間中。當物體變大時，這種操作變得越來越昂貴。這解釋了爲什麼時間不會線性增長但呈指數增長：分配 - 複製步驟在新分配空間的大小上不是線性的，因此運行時間也與循環的大小不成線性關係。