Khi một thuật toán chứa cấu trúc điều khiển lặp như vòng lặp while hoặc for, thời gian thực hiện của nó có thể được diễn tả dưới dạng tổng của các lần bỏ ra cho mỗi đợt thi hành của thân vòng lặp* Ví dụ, trong Đoạn 1.2 ta thấy lần lặp lại thứjcủa tiến trình sắp xếp chèn chiếm một thời gian tỷ lệ với jtrong ca xấu nhất. Qua việc cộng dồn thời gian bỏ ra cho mỗi lán lặp lại, ta có phép lấy tổng[summation] (hoặc chuỗi) ịj- ./=2
Đánh giá phép lấy tổng này đã cho ra một cận của 0(/7:) dựa trên thời gian thực hiện trường hợp xấu nhất của thuật toán. Ví dụ này nêu rõ tầm quan trọng chung của việc hiểu rõ cách điều tác và định cận các phép lấy tổng, (Như sẽ thây trong Chương 4, các phép lấy tổng cùng nảy sinh khi ta dùng một số phương pháp nhất định để giải quyết các phép truy toán.)
Các tính chất và công thức lây tổng
Cho một dãy aỊf ar … con sô”, tổng hữu hạn aị + tí, + … + ữ có thể viết là
ft
ỉ>r
Ả-l
Nêu n = 0, gia trị của phép lây tổng được định nghĩa là 0. Nếu n không phải là một số nguyên, ta mậc nhận giới hạn trẽn là L/?J. Cũng vậy, nêu tổng bắt đầu bằng k = A\ ở đốXkhông phải là một sô nguyên, ta mặc nhạn giá trị ban đầu của phép lây tổng là Lvl (Nói chung, ta sẽ
đưa vào cận dưới và cận trên một cách tường minh.) Gia trị của một chuỗi hữu hạn luôn được định nghĩa kỹ, và các sô hạng của nó có thểđược cộng theo một thứ tự bất kỳ.
Cho một dãy sốar av …, tổng vô hạn dị + … có thể được viết là
ĩ“,
k=i
được diễn dịch thành lim Ta..
Nếu giới hạn không tồn tại, chuỗi sẽphân kỳ; bằng không, nó sẽhội tụ. Không phải lúc nào cũng có thể cộng các số hạng của một chuỗi hội tụ theo một thứ tự bất kỳ. Tuy nhiên, ta có thể dàn xếp lại các sô” hạng của một chuỗi hội tụ tuyệt đối, nghĩa là, một chuỗi
J ak mà chuỗi xr=i 1 aj cũng hội tụ.
Tính châ”t tuyên tính
Với bất kỳ số thực c và bất kỳ dãy hữu hạn ar av … an và bv bT …,
K
Z (cak+bk)= c Ỷ, ak+X bk•
k=I k=) k=I
Tính châ”t tuyến tính cũng được chuỗi hội tụ vô hạn tuân thủ
Tính châ”t tuyến tính có thể được khai thác để điều tác các phép lây tổng liên hợp với hệ ký hiệu tiệm cận. Ví dụ,
X0(m)) = eíi;/(*)ì •
*=1 V=1 /
Trong phương trình này, hệ ký hiệu 0 bên phía trái áp dụng cho biến k, nhưng bên phía phải, nó áp dụng cho n. các dạng điều tác như vậy cũng có thể áp dụng cho chuỗi hội tụ vô hạn.
Chuỗi cấp sô”cộng
Ta đã sử dụng phép lây tổng
£* = 1 +2 + … + H,
k= 1
khi phân tích kỹ thuật sắp xếp chèn. Nó là một chuỗi cấp số cộng [arithmetic series] và có giá trị
« 1
ỵ,k = Jii(n +1) (3.1)
k= I
= Q(n2) . (3-2)
Chuỗi cấp sô”nhân
Với số thực X t* 1, phép lấy tổng k=0 là một chuỗi cấp số nhân hoặc chuỗi ỉũy thừa và có giá trị