Full width home advertisement

Travel the world

Climb the mountains

Post Page Advertisement [Top]

Complexity of an algorithm

Introduction
An algorithm is a mathematical method for calculating or computation (The computation of a function), and which can be carried out mechanically, without thinking. Algorithm complexity is concerned about how fast or slow performing specific algorithm. We define complexity as a numerical function T (n) - time in relation to the input size n. We want to specify a time in which there is no algorithm depends on implementation details. But you agree that T (n) is dependent on the performance! A specific algorithm is different amount of time to both inputs depending on factors such as processor speed; instruction set, disk speed, brand and compilers etc. The way around is to estimate the efficiency of each algorithm asymptotically. We will take time to measure T (n) the number of elementary "steps" (defined in any way), provided that each such step lasts for a constant time.

Let us consider two classic examples: adding two numbers. We will add two integers digit by digit, and it will define a "step" in our computational model. That is why we say that the addition of two n-bit integers taking steps n. Accordingly, the total computation time is T (n) = n * c, where c is the time that the addition of two bits. In different computers can addition of two pieces different time seizures, C1 and C2 say, making the addition of two n-bit integers takes T (n) = c1 * n and T (n) = C2 * n, respectively. It shows that various machines of different slopes, but the time T (n) grows linearly increases as input magnitude.

No comments:

Post a Comment

Bottom Ad [Post Page]

| Designed by Colorlib