Array list: number: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
(2 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Videos]] | |||
{{#ev:youtube|https://www.youtube.com/watch?v=uYTck0kDvl4|500|right||frame}} | |||
'''Algorithmic problem:''' [[Ordered sequence#Number|Ordered sequence: number]] | '''Algorithmic problem:''' [[Ordered sequence#Number|Ordered sequence: number]] | ||
Line 46: | Line 48: | ||
==Complexity== | ==Complexity== | ||
'''Statement:''' Linear in the length of the sequence in the worst case ( | '''Statement:''' Linear in the length of the sequence in the worst case (if the arrays of all array list items have identical lengths). | ||
'''Proof:''' Obvious. | '''Proof:''' Obvious. | ||
==Further information== | ==Further information== |
Latest revision as of 23:10, 19 June 2015
Algorithmic problem: Ordered sequence: number
Prerequisites:
Type of algorithm: loop
Auxiliary data:
- A pointer
of type "pointer to array list item of type ". - A counter
.
Abstract view
Invariant: After
- The pointer
points to the array list item at position (or is void if there is no such item). - The value of
is the sum of the values n of all array list items at positions .
Variant:
Break condition: It is
Induction basis
Abstract view: Initialize
Implementation:
- Set
first. - Set
.
Proof: Nothing to show.
Induction step
Abstract view: Add the number of elements in the current array and then go forward.
Implementation:
- If
void, terminate the algorithm and return the value of . - Otherwise:
- Set
.n. - Set
.next.
- Set
Correctness: Nothing to show.
Complexity
Statement: Linear in the length of the sequence in the worst case (if the arrays of all array list items have identical lengths).
Proof: Obvious.