الكلف المستهلكة واختيار الخوارزمية

def doubling_model(n):
    if type(n) is not int or n < 0:
        raise ValueError("Count must be a nonnegative integer")
    size = capacity = cost = 0
    resizes = []
    for _ in range(n):
        if size == capacity:
            new_capacity = max(1, 2 * capacity)
            cost += size
            resizes.append((size, new_capacity))
            capacity = new_capacity
        size += 1
        cost += 1
    return cost, resizes

print(doubling_model(8))
print(doubling_model(0))

(15, [(0, 1), (1, 2), (2, 4), (4, 8)])
(0, [])

تكلف ثماني كتابات وسبعة عناصر منسوخة 15 في هذا النموذج. ولا يُقاس حجم تخصيص أثناء التشغيل أو زمن اختبار معياري.

class TwoStackQueue:
    def __init__(self):
        self.incoming, self.outgoing = [], []
        self.moves = 0
    def push(self, value):
        self.incoming.append(value)
    def pop(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())
                self.moves += 1
        if not self.outgoing:
            raise IndexError("Queue is empty")
        return self.outgoing.pop()

queue = TwoStackQueue()
queue.push("A")
queue.push("B")
first = queue.pop()
queue.push("C")
second, third = queue.pop(), queue.pop()
print(first, second, third)
print(queue.moves)

A B C
3

تنتظر C بينما توجد B بالفعل في المكدس الصادر. وتنتقل كل من A وB وC مرة واحدة، فيُحفظ ترتيب FIFO.