[내배캠 회고록] 나의 여섯번째 회고록

어서와 알고리즘은 처음이지..?//..//

오늘은 자바 + 알고리즘 강의를 들었다. 

자바는 기존에 알고있던 기본기가 있었기 때문에 강의를 듣는데 어려움 없었다. 

그러나 알고리즘은 고등학교 이후로 처음으로 다시 접했기 때문에 새롭게 알게된 내용이 있다. 

 그중에서도 '시간 복잡도'와 '공간 복잡도'에 대해서 알게 되었는데 

예전는 링크드 리스트, 이진 탐색 정도만 공부하고 지나쳤었던거에 비하면

내가 알지 못하는 알고리즘도 종류가 다양했다는 것을 알게 되었다. 

 

아직 알고리즘 강의를 많이 들은 건 아니지만 알고리즘에서 가장 중요한 건 ''효율" 인 것 같다.

이러한 시간적으로 공간적으로 모두를 만족 시키는 코딩을 하기 위해서는 부단이 노력하고 

계속해서 연습해야겠다는 생각이 든다.

(이것이 바로 개발자의 숙명?!)

 

 

#시간 복잡도(Time Complexity)

- 입력 값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 를 의미한다

- 시간 복잡도는 Big-O 표기법을 사용하여 나타낸다

# 시간 복잡도를 표기하는 방법

• Big-O(빅-오) ⇒ 상한 점근
• Big-Ω(빅-오메가) ⇒ 하한 점근
• Big-θ(빅-세타) ⇒ 그 둘의 평균
• 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법

# Big-O 표기법의 종류

1. O(1) : 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.
2. O(n) :  O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
3. O(log n) : O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
4. O(n2) : O(n2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
5. O(2n) : O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

 

# 공간 복잡도(Space Complexity)

- 공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념.

- 보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간 그렇기 때문에 입력 공간(input size)을 고려하지 않음.

- 공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼친다.

 

# 정리

• 시간과 공간은 반비례적 경향이 있음
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
• 알고리즘은 시간 복잡도가 중심

 

 

@출처 : https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

@출처 :https://yoongrammer.tistory.com/79

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

 

https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Algorithm] 시간 복잡도, 공간 복잡도