Let's talk about algorithms
Let's talk about algorithms
What is an algorithm?
An algorithm is a set of instructions for solving a problem or accomplishing a task. So if you think about wanting to achieve a B.Sc degree(I don’t know why I picked this example so please don’t judge.) ,This is a task, You gotta do it or you can take it as a problem you know more or less we all hate study 😂. To achieve this goal you need to pass all the exams like PSC , JSC, SSC, HSC (In case of Bangladesh)and also need to do hard study on coachings etc. You can consider this as the “Set of instructions”. And at the end you can call it an algorithm for achieving a B.Sc Degree.
Most importantly, it's not a language that a computer can understand by writing it on your computer. We can just simply use any symbols or language to represent instructions.
Complexities of an algorithms
The complexity of algorithms depends on how much time and the space it takes to solve a problem for N number of input. We can divide it into two types: Time Complexity and Space Complexity.
Let's talk about time complexity
It’s a process of defining the formula of prediction of how much time is required for the execution of those algorithms.
If a person has a task to clean a room. And that man took 5 minutes to complete that particular task. In algorithms, we call that Time Complexity that task.
Let's talk about Space Complexity
It's a process of defining how much memory an algorithm will use for the execution of the algorithms.
I know you might have heard that software requires 2GB ram etc. in software requirement for your system while you buy software or games. We know software is running a lot of algorithms behind the scenes. We can predict that by calculating the Space Complexity of each algorithm going to use in our software.
Asymptotic Analysis
So this idea comes from the analysis of many programs which one runs faster than the others in terms of large input. Like if you run two test with two different searching algorithm like learner search and binary search.
So lets uncomment the learner search code and check the output :
#include <iostream>
#include <chrono>
using namespace std;
class searchingAlgos{
public:
//LINEAR SEARCH
int linearSearch(int *arr, int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
//BINARY SEARCH
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
};
int main(){
int arr[1000000];
int n;
cin>>n;
for(int i=0; i<n; i++){
arr[i] = i;
}
searchingAlgos s;
int start_s=clock(); //CLOCK START
cout<<s.linearSearch(arr, n, n-1)<<endl;
//cout<<s.binarySearch(arr, 0, n-1, n-1)<<endl;
int stop_s=clock(); //CLOCK STOP
cout << "time: "<<(stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
}
Result: 999998
Time : 3.086 sec
And then lets uncomments the binary search code :
#include <iostream>
#include <chrono>
using namespace std;
class searchingAlgos{
public:
//LINEAR SEARCH
int linearSearch(int *arr, int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
//BINARY SEARCH
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
};
int main(){
int arr[1000000];
int n;
cin>>n;
for(int i=0; i<n; i++){
arr[i] = i;
}
searchingAlgos s;
int start_s=clock(); //CLOCK START
cout<<s.binarySearch(arr, 0, n-1, n-1)<<endl;
int stop_s=clock(); //CLOCK STOP
cout << "time: "<<(stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
}
Result: 999998
Time : 0.03
In both cases, we used input number: 999999.
And you can see the result. There's a huge difference between the two outputs. So the big idea is to handle such issues in analyzing algorithms. We can evaluate the performance of an algorithm. We can calculate how the time or the space in terms of input size increase with the input size.
It's not the perfect analyzing method for all types of algorithms. But it's the best analyzing method for now. So we can say that which software or the algorithm is asymptotically slower, always performs better for your particular situation.
Now How its impact on our regular life
So algorithms are things that we use in our real life in almost every term. Let me introduce you to some of them :
Google Search
Even an action as seemingly simple as a Google search is only possible with the help of algorithms. Say, for example, you want to know if an elephant can swim. How you phrase the question to Google is the input you are asking the computer to determine.
Sorting Papers
Magine a teacher sorting their students’ papers according to the alphabetical order of their first names. This type of task is similar to the function of a sorting algorithm, like a bucket sort. By looking at only the first letter of the first name, you can remove a lot of unnecessary information. This is an automated process that makes sorting more efficient.
And there are more examples like this. I know the article is long. So I want it to end here. In the next article, I will explain some searching algorithms. Till then stay safe. Thank you.
About us
Banner ad
