Saturday, 3 December 2016

Complexity of an algorithm

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:
Write comments

Theme images by MichaelJay. Powered by Blogger.

Follow by Email

Social stratification

Definition Social stratification is one of the results of ongoing social processes taking place. Every society is segmented into differen...