10.6 Algorithms

An algorithm is a step-by-step procedure for computing a desired result. The complexity of algorithms may be defined in many ways, but the most common is time complexity, the amount of execution time required to compute the desired result. Algorithmic complexity is expressed using the "order of" notation. Common algorithmic complexities are

• O(c)

• O(log₂n)

• O(n)

• O(n log₂n)

• O(n²)

• O(n³)

where c is a constant and n is the number of elements participating in the algorithmic computation.

All algorithms with the same complexity differ from each other only by a multiplicative and additive constant. Thus, it is possible for one O(n) algorithm to perform 100 times faster than another O(n) algorithm and be considered of equal time complexity. It is even possible for an O(n²) algorithm to outperform an O(c) algorithm for sufficiently small n. The algorithmic complexity is most useful when the number of entities being manipulated is large (as in "asymptomatically approaching infinity") because then these constants become insignificant and the complexity order dictates performance. For small n, they can only given rules of thumb.

Execution time is not the only optimization criteria applied to systems. Objects may be designed to optimize

• Runtime performance

  • Average performance

  • Worst-case performance

  • Deterministic (predictable) performance

• Runtime memory requirements

• Simplicity and correctness

• Development time and effort

• Reusability

• Extensibility

• Reliability

• Safety

• Security

Of course, to some degree these are conflicting goals.^[8] For example, some objects must maintain their elements in sorted order. A Bubble sort is very simple, so it requires a minimum of development time. Although it has a worst-case runtime performance of O(n²), it can actually have better performance than more efficient algorithms if n is small. Quicksort is generally much faster O(log₂n) in the normal case, and O(n²) in the worst case but is more complicated to implement. It is not always best to use a Quicksort and it is not always worst to use a Bubble sort even if the Quicksort is demonstrably faster for the data set. Most systems spend most of their time executing a small portion of the code. If the sorting effort is tiny compared to other system functions, the additional time necessary to correctly implement the Quicksort might be more profitably spent elsewhere.

^[8] Which is why they are called tradeoffs.

Some algorithms have good average performance but their worst-case performance may be unacceptable. In real-time systems, raw performance is usually not an appropriate criterion deterministic performance is more crucial. Often, embedded systems must run in a minimum of memory, so that efficient use of existing resources may be very important. The job of the designer is to make the set of design choices that results in the best overall system, and this includes its overall characteristics.

Classes with rich behavior must not only perform correctly, they must also be optimal in some sense. Most often, average execution speed is the criterion used for algorithm selection, but as we saw in Section 10.1, many other criteria may be used. Once the appropriate algorithm is selected, the operations and attributes of the class must be designed to implement the algorithm. This will often result in new attributes and operations that assist in the execution of the algorithm.

For example, suppose you are using the container pattern and decide that a balanced AVL tree container is best.^[9] An AVL tree, named after its inventors Adelson, Velskii, and Landis, takes advantage of the fact that the search performance of a balanced tree is O(log₂n). A balanced binary tree is one in which all subtrees are the same height ±1. Each node in an AVL tree has a balance attribute,^[10] which must be in the range [ 1, 0, +1] for the tree to be balanced. The problem with simple trees is that their balance depends on the order in which elements are added. In fact, adding items in a sorted order to an ordinary binary tree results in a linked list, with search properties of O(n). By balancing the tree during the addition and removal of items, we can improve its balance and optimize its search performance.

^[9] An AVL tree is not a specifically real-time example, but the algorithm is well known in the computer science literature and is quite straightforward. Thus, we will use it here for our discussion.

^[10] This is a derived attribute. It can be explicitly stored and maintained during addition and deletion, or it can be recomputed as necessary.

Let's assume that we want an in-order tree that is a tree in which a node is always "greater than" its left child and "less than" its right child, such as the one shown in Figure 10-3. Note that node 10 is greater than its left child (6) and less than its right child (12). If we now add a 9 to the tree, we could make it the left child of node 10 and the parent of node 6. But this would unbalance the tree, as shown in Figure 10-4. If we then balance the tree we might end up with a tree such as the one in Figure 10-5.

Figure 10-3. Balanced In-Order Tree

Figure 10-4. Unbalanced Tree after Adding Node 9

Figure 10-5. Rebalanced Tree

AVL trees remain balanced because whenever a node is inserted or removed that unbalances the tree, nodes are moved around using techniques called tree rotations to regain balance. The algorithm for adding a node to an AVL tree looks like this:

1. Create the new node with NULL child pointers, set the attribute Balance to 0.

2. If the tree is empty, set the root to point to this new node and return.

3. Locate the proper place for the node insertion and insert.

4. Recompute the balance attribute for each node from the root to the newly inserted node.

5. Locate an unbalanced node (balance factor is ±2). This is called the pivot node. If there is no unbalanced node, then return.

6. Rebalance the tree so that it is now balanced. There are several situations:

   1. Pivot has a balance of +2. Rotate the subtree based at the Pivot left.

   2. Pivot has a balance of 2. Rotate the subtree based at the Pivot right.

7. Continue balancing subtrees on the search path until they are all in the set [-1, 0 +1].

Rotating left means replacing the right child of the pivot as the root of the subtree, as shown in Figure 10-6. Right rotations work similarly and are applied when the balance of the pivot is 2. Many times, double rotations are required to achieve a balanced tree, such as a left-right or a right-left rotation set.

Figure 10-6. Left Rotation

The set of operations necessary to meet this algorithm are

 typedef class node { public:     data d; // whatever data is held in the tree nodes     int balance; // valid values are  1, 0 , 1     node* leftPtr;     node* rightPtr; } * nodePtr; class avlTree {     nodePtr root;     void rotateLeft(nodePtr n);     void rotateRight(nodePtr n); public:     void add(data a);     void delete(data a);     nodePtr find(data a); }; 

Structured English and pseudocode, as shown above, work perfectly well in most circumstances to capture the essential semantics of algorithms. The UML does define a special kind of state diagram, called an activity diagram, which may be helpful in some cases.

Activity diagrams depict systems that may be decomposed into activities roughly corresponding to states that mostly terminate upon completion of the activity rather than as a result of an externally generated event. Activity diagrams may be thought of as a kind of flowchart where diagrammatic elements are member function calls. Figure 10-7 shows the activity diagram for the addNode() operation of our AVL tree class.

Figure 10-7. Activity Diagram for Add Node Operation