Array list: number: Difference between revisions

From Algowiki
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 (for an arbitrary, yet fixed, identical length of the arrays of all array list items).
'''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:

  1. A pointer p of type "pointer to array list item of type K".
  2. A counter cN0.

Abstract view

Invariant: After i0 iterations:

  1. The pointer p points to the array list item at position i+1 (or is void if there is no such item).
  2. The value of c is the sum of the values n of all array list items at positions 1,...,i.

Variant: p is moved one step forward so as to point to the next array list item.

Break condition: It is p= void.

Induction basis

Abstract view: Initialize p so as to point to the first array list item.

Implementation:

  1. Set p:=first.
  2. Set c:=0.

Proof: Nothing to show.

Induction step

Abstract view: Add the number of elements in the current array and then go forward.

Implementation:

  1. If p=void, terminate the algorithm and return the value of c.
  2. Otherwise:
    1. Set c:=c+p.n.
    2. Set p:=p.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.

Further information