[질문]cost amortizatoin, amortized complexity

algorithm이나 data structure 책에 나오는 'amortize'라는 단어는

어떤 식으로 이해해야 할까요?

(사전에는 할부, 양도하다.)

제 생각에는

어떤 알고리즘 k가 a operation에는 O(n), b operation은 O(1)이 걸릴 때

amortize하여 = 각 operation이 trade off를 통해 변형하여 (k => k')

변화된 알고리즘 k'은 a operation이 O(log(n)) 쯤 걸리고

b operation은 O(log(n) ^ 2) 쯤 걸리게 만들었다.

라고 생각되는 데요. 맞는 건가요?


그럼

"sequential한 queue structure의 경우 insert는 O(1), search는 O(n)인데

amortize하여 heap으로 만들었더니, 두 operation모두 O(log(n))이 되었다."

라고 해도 되나요?