----------------------------------------------------------------------
Hello, i am GameDeveloperPlayground.
I am a Korean student and I post it for English practise.
I would appreciate pointing out grammar or typos.
----------------------------------------------------------------------
In this post, about Fibonacci sequence.
Fibonacci sequence
Fibonacci sequence is that adds the previous two numbers to create the number of current positions.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...
Except for the start two numbers 0 and 1, summarize the total number of previous number and previous number at previous number atfer the third.
0, 1, (0+1) , ((0+1) + 1) , (((0+1) + 1) +(0+1)) ...
There are a number of ways to implement such a simple algorithm.
Fibonacci sequence implementation using recursive function call.
1 2 3 4 5 6 7 8 | int Algorithm(int n){ if (n == 1) return 0; else if (n == 2) return 1; else return Algorithm(n - 1) + Algorithm(n - 2); } | cs |
The first and second values are set to 0 and 1, respectively returning 0 and 1, and returning the sum of the previous of n and the previous of the previous of n.
have just completed implementation, but every time enter the Algorithm function need to check wgether n is 1 or 2.
have implemented it as a loop this time to remove the fuplicate test twice.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | int Algorithm(int n){ if (n == 1) return 0; else if (n == 2) return 1; else { int beforevalue = 0; int current = 1; for(int i=1; i<n; ++i) { int temp = current; current += beforevalue; beforevalue = temp; } return current; } } | cs |
Changed the part that calls tell recursive function to thefor statement.
Current is the current number, and befroevalue is the previous number.
The next number is the current number plus the previous number. so you can add current and before value.
Other ways to do it... Similar in performance, but there is another ' tail recursion' implementation. in code.
1 2 3 4 5 6 7 8 9 10 | int Algorithm(int n){ return AlgorithmTail(n, 0, 1); } int AlgorithmTail(int n, int before, int next){ if (n == 0) return before; else return AlgorithmTail(n - 1, next, before + next); } | cs |
After one hour
Before is next
Next is before + next.
So iterates through the tail recursion function and returns the current value (before) if the value of n is zero.
We will discuss the tail recursive function in detail in another post.
Thank you.
'Programing > Algorithm' 카테고리의 다른 글
| [Algorithm] About Select Sort (0) | 2016.12.08 |
|---|---|
| [Algorithm] About Insertion Sort (0) | 2016.12.08 |
| [Algorithm] About Bubble Sort !! (0) | 2016.12.08 |
| [Algorithm] About Linear Search (0) | 2016.12.08 |
| [Algorithm] About Binary Search Algorithm. (0) | 2016.12.08 |
----------------------------------------------------------------------
Hello, i am GameDeveloperPlayground.
I am a Korean student and I post it for English practise.
I would appreciate pointing out grammar or typos.
----------------------------------------------------------------------
In this post, about asymptotic notation.
Most algorithms end quickly if the input size is small, regardledd of the efficiency of the algorithm.
But, if the input size is large, will be a difference in speed. Therefore, when analyzing the execution time of the algorithm, always analyze the inpust size large enough. This is called asymprotic nanlysis.
Typically, there are five notations.
- Big O notatios.
- Small O notiations.
- Omega notiations.
- Little Omega notations,
- theta notation.
Let me write one by one.
Bit O notation
Big O notation is used computher enginerring to express the complexty or performance of an algorithm.
Big O notation represents the worst case.
O(1)
O(1) means that the execution time(or space) of the algorithm is always the same regardless of the size of the input data.
1 2 3 4 5 6 7 8 | bool IsNull(int[] intarrays) { if (intarrays == null) { return true; } return false; } | cs |
In this case, the if statement is executed on once regardless of the size of the input intarrays.
O(N)
O(N) means that the processing time increases proportionally to the amount of Input.
1 2 3 4 5 6 7 8 9 10 11 | bool IsNull(int[] intarrays, int index) { for(int i = 0; i < intarrays.Length; ++i) { if (intarrays[i] == index) { return true; } } return false; } | cs |
In this case. intarrays[i] and index value may be equal to each other in the middle.
Remember, Big O notations is represents performance for the worst case.
This is, the limits value that assumes that the maximum iteration
O(N²)
O(N²) represents a situation where performance is increased in proportion to the power of the power of the size of the input data
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | bool IsNull(int[] intarrays, int index) { for(int i = 0; i < intarrays.Length; ++i) { for(int j = 0; j < intarrays.Length; ++j) { if (intarrays[j] == index) { return true; } } } return false; } | cs |
In this case, this is typically the case when nested loops are performed od data values thar are predominant.
O(log N)
O(log N) represent a case where the processing time increases slightly depending on the size of the input data.
A binary search algorithm is typical!!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | int searchint(int* intarrays, int index) { int from = 0; int to = intarrays.Length - 1; while (from <= to) { int mid = (from + to) / 2; if (intarrays[mid] > index) { to = mid - 1; } else if (intarrays[mid] < index) { from = mid + 1; } else { return mid; } } return -1; } | cs |
Most algorithms have good algorithms.
O(2ⁿ)
O(2ⁿ) represents the case where the processing time increases by 2times every time the input data increases by one.
O(2ⁿ) is called worst algorithm.
The big O signs are summarized as follows.
O(1) < O(log N) < O(N) < O(N²) < O(2ⁿ)
Little o Notation
Little o notation is used to express upper bounds that are more spacious than Big O notation.
Little o notation is not often used to indicate the complexity or performance of an algorithm.
If the analysis time of an algorithm is O(log N), this means that the time required for the algorithm increases slowly over log N for Input size N.
It was hard to understand....
Which means it does not increase like log N, but increases like log N. O(log N) and o(log N) can not be the same growth rate, are used when it is obvious that they increase more slowly than log N.
Big Omega(Ω) notation
Big Omega notation, like Big O notation, is used to denote algorithm complesity or performance.
However, if Bit O notation is the worst, Bit Omege notation represents the best case.
This is the minimum time it takes to execute the corresponding algorithm.
Little Omega(ω) notation
Little Omega notation is used to represent upper bounds that are more spacius than Big Omega notation.
Like the Little O notation.
If the analysis time of an algorithm is ω (log N), this means that the time required for the algorithm to grow slowly over log N for input size N.
It was hard to understand, which means it does not increase like log N, but increases like log N. That is, Ω (log N) and ω (log N) can not be the same rate of increase, but they are used when it is obvious that they will grow more slowly than log N.
Theta(Θ) notation
Theta notation.. Big O notation is worst case, and Big Omega notation is best case. Then Theta notation is average case.
Think it is the intersection of Big O and Big Omega.
So, this algorithm is within the theta range no matter hou good or bad it is, It's mean.
I've written a bit about asymptotic notation.
I'm not sure about the other four notations except for Big O.
In the future, I will post each of these 5 pieces one by one.
Thank you.
----------------------------------------------------------------------
Hello, i am GameDeveloperPlayground.
I am a Korean student and I post it for English practise.
I would appreciate pointing out grammar or typos.
----------------------------------------------------------------------
In this post I will post about inline, one of the reserved words in C++
This is one of the reserved words that comes out when you look at c++ books.
To put it plainly, inline functions are where the coded of the complied function is inserted directly into the program's code.
Shall see the code?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include<iostream> using namespace std; inline void Inlinefuction() { cout<<"*** Inlinefuction() ***"<<endl; } int main() { Inlinefuction(); return 0; } | cs |
When you compile the code.
1 2 3 4 5 6 7 8 9 10 11 | #include<iostream> using namespace std; int main() { cout<<"*** Inlinefuction() ***"<<endl; return 0; } | cs |
It will changed as above. How about this?
Let's check with assembly code to see more results.
First, if you look at the main function of assembly code that is not inline.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | ; 12 : { push ebp mov ebp, esp ; 13 : Inlinefuction(); call ?Inlinefuction@@YAXXZ ; Inlinefuction ; 14 : return 0; xor eax, eax ; 15 : } cmp ebp, esp call __RTC_CheckEsp pop ebp ret 0 | cs |
Will come out as above.
Inline apply assembly code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | ; 12 : { push ebp mov ebp, esp push esi ; 13 : Inlinefuction(); mov esi, esp mov eax, DWORD PTR __imp_?endl@std@@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@1@AAV21@@Z push eax push OFFSET ??_C@_0BI@FMEKNHNP@?$CK?$CK?$CK?5Inlinefuction?$CI?$CJ?5?$CK?$CK?$CK?$AA@ mov ecx, DWORD PTR __imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A push ecx call ??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char> > add esp, 8 mov ecx, eax call DWORD PTR __imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QAEAAV01@P6AAAV01@AAV01@@Z@Z cmp esi, esp call __RTC_CheckEsp ; 14 : return 0; xor eax, eax ; 15 : } pop esi cmp ebp, esp call __RTC_CheckEsp pop ebp ret 0 | cs |
Come out like this.
Look at line 13, can see the difference.
Let's change the function more easily.
Source code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include<iostream> using namespace std; int Inlinefuction(int a, int b) { return a+b; } int main() { int n; n = Inlinefuction(1,2); return 0; } | cs |
Assembly code not use Inline.
1 2 3 4 5 6 7 8 9 10 11 12 | ; 13 : int n; ; 14 : n = Inlinefuction(1,2); push 2 push 1 call ?Inlinefuction@@YAHHH@Z ; Inlinefuction add esp, 8 mov DWORD PTR _n$[ebp], eax ; 15 : return 0; xor eax, eax | cs |
Assembly code use Inline.
1 2 3 4 5 6 7 8 9 10 | ; 13 : int n; ; 14 : n = Inlinefuction(1,2); mov eax, 1 add eax, 2 mov DWORD PTR _n$[ebp], eax ; 15 : return 0; xor eax, eax | cs |
Look at code 14, can feel the difference.
No call on the assembly code.
And push is not being called either.
Looking at the process of calling a generic function, first the stack is push parameters, and the function is called.
Then there are push and pop stack for the return value in the function. After return, there is pop for stack cleanup.
Because these function calls access the stack, they can slow down, because accessed by memory.
When use inline, the first thing is speed and memory effect.
Disadvantage is that if use it repeatedly, the assembly code becomes longer.
If the function is called multiple times and written in assemblycode.. is not that a joke?
Conclusion.
Well, my conclusion from my brief knowledge.
Function that has a short syntax and fewer calls is use inline.
I would appreciate it if you point out in a comment field. please.
Thankyou.
'Programing > Language' 카테고리의 다른 글
| Why learn C language. (0) | 2016.11.30 |
|---|
