Пожалуйста, обратитесь к ответу 2 материала выше.Я могу следить за текстом до этого момента.Кажется, я всегда теряю концептуализацию, когда нет иллюстрации, возможно, из-за того, что я новичок в математической нотации.
Я понимаю стоимость дорогостоящей операции (удвоение массива, когда стек заполнен)
1 + 2 + 4 + 8 + ... + 2 ^ i, где i - индекс этой последовательности.Таким образом, индекс 0 = 1, 1 = 2, 2 = 4 и 3 = 8.
Я вижу последовательность дорогостоящих операций, но меня смущает следующее объяснение.
Теперь в любой последовательности из n операций общая стоимость изменения размера составляет 1 + 2 + 4 + 8 + ... + 2 ^ i для некоторого 2 ^ i
Дон.Не понимаю это объяснение?
Общая стоимость для изменения размера составляет 1 + 2 + 4 + 8 + ... + 2 ^ i для некоторых 2 ^ i
Что это означает для некоторых 2^i < n
говорит ли это, что число операций n всегда будет больше, чем 2 ^ i?и n обозначает число операций или длину массива?
И следующее, за которым я просто не следую:
если все операции являются толчками, то 2 ^ iбудет наибольшая мощность 2 меньше, чем п.Эта сумма не более 2n - 1.
Может кто-нибудь проиллюстрировать это, пожалуйста?