점근 표기법 (Big-O 표기법) 과 알고리즘

개요.

이해하기 어렵게 적어둔 글들이 대다수라서, 가능한 알아듣기 쉽게, 재정리하여 적고자 함.

 

해당 개념이 등장하는 곳:

CS (컴퓨터 사이언스, 알고리즘?)

 

이 글의 단점:

아직은 필자 위주로 적다보니 영어로 적혀 있음. 혹시 절박하게 이 개념을 찾다가 여길 왔다면 정말 미안합니다.

 

Executive summary:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. 

 

My note:

O(n) is the representative symbol of this Big-O notation concept. The O comes from the order of magnitude of complexity. Complexity is relative to other search algorithms. This is useful when only comparing amongst algorithms that solves the same problem. The (n) represents a function of the size. Big O meausres complexity as the input size grows. For (n)'s perspective, understanding how an algorithm performs in all possible data sets (rather to understands in a single data set). This Big O can also be viewed as upper bounds algorithm. It measures how the algorithm performs in the worst case scenario.

 

logarithmic runtime be represented as Big O - O(log n) or O(in n).

 

Big O as 'a time complexity of Big O, and n with parenthesis'. Which is O(n) and this is linear search.

In binerary search, O(log n). Just added log in the parenthesis.

 

Keyword: common complexities, common values of Big O, time complexities, space(?) complexities, O(log n) or O(in n). Sublinear or linear, logarithmic runtime.

 

---

Purpose of applying this concept:

In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.[3] In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem. Big O notation is also used in many other fields to provide similar estimates.

 

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

Big O notation - Wikipedia

Useful source: