Big O Notation

Objectives

• Motivate the need for something like Big O Notation

• Describe what Big O Notation is

• Simplify Big O Expressions

• Define "time complexity" and "space complexity"

• Evaluate the time complexity and space complexity of different algorithms using Big O Notation

• Describe what a logarithm is

1. what is Big O Notation ?

Imagine we have multiple implementations of the same function. How can we determine which one is the "best?"

1-1 what is Big O Notation ?

빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다.

알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.

빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.

시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.

시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 
빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.