豪鬼メモ

一瞬千撃

Entries from 2020-07-31 to 1 day

reallocによる配列拡張の償却時間計算量

reallocを使ってメモリアロケーションのサイズを少しずつ伸ばしていく際に、償却時間計算量はO(N)になるだろうか、それともO(N^2)だろうか。結論としては、普通にやるとO(N^2)になる。ただし、セオリー通りにアプリケーション側で工夫するとO(N)にできる。性…