Data Structure - Big O Theory

peoplesuc

Spy
Joined
Jul 9, 2003
Messages
170
Reaction score
0
After a general grasp of the syntax in C++ you need to learn how to choose between algorithms for a problem. There is a benefit to efficient algorithms. The benefit being computing time. One way can take a few miliseconds and another way can take YEARS!

'X to the power of 10'(X^10' might be greater then '10 to the power of X'(10^X) when X is 2. But at a certain point 10^X surpasses X^10. X=10 is that point.

To guage the overall efficiency of an algorithm you use 'Big O'. No not that cartoon on Adult Swin on Cartoon Network. O(n) <-- thats what it looks like.

Lets look at an example to get a general idea of how to use all this.

...
for(int i = 0; i<2; i++)
{
for(int j = 0; j<2; i++)
{
cout << i << " " << j << endl;
}
}
...

/*OUTPUT:
...
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
...
*/

This is a nested 'for loop'. A 'for loop' inside a 'for loop'. Lets say one loop is X. If you have 2 loops right after each other then its just X + X. If they are nested then it's X * X. So for the above example the Big O would be O(X^2).

Not very efficient but it's a start.

This is not the best guide to data structures. It is just a VERY BASIC guide to get people interested in programming. I've been up for 34 hours straight so my thinkings really poor. I want some feed back.
 
You're not actually covering datastructures, you're covering the analysis of algorithms with this post.
 
peoplesuc said:
After a general grasp of the syntax in C++ you need to learn how to choose between algorithms for a problem. There is a benefit to efficient algorithms. The benefit being computing time. One way can take a few miliseconds and another way can take YEARS!

'X to the power of 10'(X^10' might be greater then '10 to the power of X'(10^X) when X is 2. But at a certain point 10^X surpasses X^10. X=10 is that point.

To guage the overall efficiency of an algorithm you use 'Big O'. No not that cartoon on Adult Swin on Cartoon Network. O(n) <-- thats what it looks like.

Lets look at an example to get a general idea of how to use all this.

...
for(int i = 0; i<2; i++)
{
for(int j = 0; j<2; i++)
{
cout << i << " " << j << endl;
}
}
...

/*OUTPUT:
...
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
...
*/

This is a nested 'for loop'. A 'for loop' inside a 'for loop'. Lets say one loop is X. If you have 2 loops right after each other then its just X + X. If they are nested then it's X * X. So for the above example the Big O would be O(X^2).

Not very efficient but it's a start.

This is not the best guide to data structures. It is just a VERY BASIC guide to get people interested in programming. I've been up for 34 hours straight so my thinkings really poor. I want some feed back.

Errr your confuseing me, this is a data structure???

http://www.cplusplus.com/doc/tutorial/tut3-5.html

As far as I can tell you seem to be talking about optimization, which is good but the names misleading.
 
Same guy that did the first post on "How to write classes"... man was that bad.
 
Yeah...I'm in a data structures class right now...

You are describing Big-O but it is not a data structure... A data structure is somthing like a Stack or a Queue. Both forms of a Linked List. There are many other examples of a data structure, additionally it is very simple to create your own.
 
i'll give 'im this much, Big O is related to data structures, knowing your access times to elements is very important when deciding which data structure to use for what purpose
 
Its not so much acess times as it is running times... for example if you have a sorting algorithm which is O(n^2) it would be much better to use a sort which is O(n) where n is the number of elements. mergesort( i believe O(nlog(n))) is better than bubblesort(O(n^2)).
 
Back
Top