Since we're in the era where we deal with LOTS and lots of information, we need some efficient ways to deal with them. In computer science, we will learn how to manipulate data and/or solve computational problems (like algorithm) in data structure!
Think of the library, it would take you all day (at least) to find a book in a messy library. But if every position of the books is marked and recorded, or the books are neatly arranged, then it would take less than a minute to find a book!
Now, this post will cover an introduction of array and big O notation (Asymptotic Upper Bound). Let's start with Big O.
- Talks about time and space.
- We use the term big O -> Asymptotic Upper Bound (Big O notation)
- The greatest or maximum term in function
- Transitivity : if f(n) = O(g(n)), and g(n) = O(h(n)), then f(n) = O(h)n)) also.
- Sums of function : if f(n) and g(n) = O(h(n)), then f(n) + g(n) = O(h(n)).
- Polynomial : let f(n) be the polynomial of degree "d", then f(n) = O(nd ).
for more information, click here!
As I've said, there really are many ways to store the data, and array is one of them. But it is the very fundamental data structure. Now let's look at its property.
- data stored contiguously
- data accessible by an index (e.g. A[i])
- The size of the array is determined beforehand (meaning it's fixed)
There are two types of array; ordered and unordered. What's the different? Well, the difference can be seen in the time and algorithm used to do some operations.
And here's the table to compare the two:
|Ordered Array||Unordered Array|
|Insertion||Slow (Because you have to search first, then you might have to move the element/data in the array to put the data in)||Quick (Just add to the latest position; O(1)|
|Searching||Quick (if you use binary search; O(logN), but still slow using linear search; O(N/2) -> average time used)||Slow (can only use linear search; O(N/2))|
|Deletion||Also Slow T_T (Search the chosen data using binary search; O( logN), delete, then move all the data1; O(N/2)||Slow (same process, except linear search; O(N))|
::Creating an array::
int intArray; intArray = new int;
int intArray = new int;
::Accessing Array elements::
temp = intArray; intArray = 7;
After the deletion, there will be a space between data, so the data has to be moved so there won't be a gap because arrays are contiguous. ↩