Array list: number: Difference between revisions
No edit summary |
No edit summary |
||
| (8 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
'''Algorithmic problem:''' [[ | [[Category:Videos]] | ||
{{#ev:youtube|https://www.youtube.com/watch?v=uYTck0kDvl4|500|right||frame}} | |||
'''Algorithmic problem:''' [[Ordered sequence#Number|Ordered sequence: number]] | |||
'''Prerequisites:''' | '''Prerequisites:''' | ||
| Line 15: | Line 17: | ||
# The pointer <math>p</math> points to the array list item at position <math>i+1</math> (or is void if there is no such item). | # The pointer <math>p</math> points to the array list item at position <math>i+1</math> (or is void if there is no such item). | ||
#The value of | #The value of <math>c</math> is the sum of the values n of all array list items at positions <math>1,...,i</math>. | ||
'''Variant:''' <math>p</math> is moved one step forward so as to point to the next array list item. | '''Variant:''' <math>p</math> is moved one step forward so as to point to the next array list item. | ||
'''Break condition:''' It is <math>p=</math> void. | '''Break condition:''' It is <math>p=</math> void. | ||
| Line 26: | Line 29: | ||
'''Implementation:''' | '''Implementation:''' | ||
# Set <math>p:= | # Set <math>p:=</math>first. | ||
# Set <math>c:=0</math>. | # Set <math>c:=0</math>. | ||
| Line 36: | Line 39: | ||
'''Implementation:''' | '''Implementation:''' | ||
# If void, terminate the algorithm and return the value of <math>c</math>. | # If <math>p=</math>void, terminate the algorithm and return the value of <math>c</math>. | ||
# Otherwise: | # Otherwise: | ||
## Set <math>c:=c+p</math>.n. | ## Set <math>c:=c+p</math>.n. | ||
| Line 45: | 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 [math]\displaystyle{ p }[/math] of type "pointer to array list item of type [math]\displaystyle{ K }[/math]".
- A counter [math]\displaystyle{ c \in \mathbb{N}_0 }[/math].
Abstract view
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:
- The pointer [math]\displaystyle{ p }[/math] points to the array list item at position [math]\displaystyle{ i+1 }[/math] (or is void if there is no such item).
- The value of [math]\displaystyle{ c }[/math] is the sum of the values n of all array list items at positions [math]\displaystyle{ 1,...,i }[/math].
Variant: [math]\displaystyle{ p }[/math] is moved one step forward so as to point to the next array list item.
Break condition: It is [math]\displaystyle{ p= }[/math] void.
Induction basis
Abstract view: Initialize [math]\displaystyle{ p }[/math] so as to point to the first array list item.
Implementation:
- Set [math]\displaystyle{ p:= }[/math]first.
- Set [math]\displaystyle{ c:=0 }[/math].
Proof: Nothing to show.
Induction step
Abstract view: Add the number of elements in the current array and then go forward.
Implementation:
- If [math]\displaystyle{ p= }[/math]void, terminate the algorithm and return the value of [math]\displaystyle{ c }[/math].
- Otherwise:
- Set [math]\displaystyle{ c:=c+p }[/math].n.
- Set [math]\displaystyle{ p:=p }[/math].next.
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.