'Computer'에 해당되는 글 1건

  1. 2016.12.07 [Computer Science] Asymptotic Notation
2016. 12. 7. 11:41

[Computer Science] Asymptotic Notation

Programing/ComComputer Science


----------------------------------------------------------------------

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.


저작자표시 비영리 변경금지
Posted by 시리시안

티스토리툴바