• Choose a category
• All
• Classic-Fiction

By Root 1483 0

for an approximation. This is true of a special class of problems called NP-complete problems (see the related topics at the end of the chapter).

Although an algorithm's complexity is an important starting point for determining how well it will perform, often there are other things to consider in practice. For example, when two algorithms are of the same complexity, it may be worthwhile to consider their less significant terms and factors. If the data on which the algorithms' performances depend is small enough, even an algorithm of greater complexity with small constants may perform better in practice than one that has a lower order of complexity and larger constants. Other factors worth considering are how complicated an algorithm will be to develop and maintain, and how we can make the actual implementation of an algorithm more efficient. An efficient implementation does not always affect an algorithm's complexity, but it can reduce constant factors, which makes the algorithm run faster in practice.

Analysis Example: Insertion Sort

This section presents an analysis of the worst-case running time of insertion sort , a simple sorting algorithm that works by inserting elements into a sorted set by scanning the set to determine where each new element belongs. A complete description of insertion sort appears in Chapter 12. The code for the sort is shown in Example 4.1.

We begin by identifying which lines of code are affected by the size of the data to be sorted. These are the statements that constitute the nested loop, whose outer part iterates from 1 to size - 1 and whose inner part iterates from j - 1 to wherever the correct position for the element being inserted is found. All other lines run in a constant amount of time, independent of the number of elements to be sorted. Typically, the generic variable n is used to refer to the parameter on which an algorithm's performance depends. With this in mind, the outer loop has a running time of T (n) = n - 1, times some constant amount of time. Examining the inner loop and considering the worst case, we assume that we will have to go all the way to the other end of the array before inserting each element into the sorted set. Therefore, the inner loop iterates once for the first element, twice for the second, and so forth until the outer loop terminates. Effectively, this becomes a summation from 1 to n - 1, which results in a running time of T (n) = (n (n + 1)/2) - n, times some constant amount of time. (This equation is from the well-known formula for summing a series from 1 to n.) Consequently:

Example 4.1. Implementation of Insertion Sort from Chapter 12

/*****************************************************************************

* *

* ------------------------------- issort.c ------------------------------- *

* *

*****************************************************************************/

#include

#include

#include "sort.h"

/*****************************************************************************

* *

* -------------------------------- issort -------------------------------- *

* *

*****************************************************************************/

int issort(void *data, int size, int esize, int (*compare)(const void *key1,

const void *key2)) {

char *a = data;

void *key;

int i,

j;

/*****************************************************************************

* *

* Allocate storage for the key element. *

* *

*****************************************************************************/

if ((key = (char *)malloc(esize)) == NULL)

return -1;

/*****************************************************************************

* *

* Repeatedly insert a key element among the sorted elements. *

* *

*****************************************************************************/

for (j = 1; j < size; j++) {

memcpy(key, &a[j * esize], esize);

i = j - 1;

/**************************************************************************

* *

* Determine the position at which to insert the