Big O 표기법

Big O 표기법은 알고리즘의 효율성을 설명하는 데 사용되는 수학적 표기입니다.

특히, 알고리즘이 어떤 입력 크기 n에 대해 얼마나 많은 연산을 필요로 하는지를 표현하는데 많이 사용됩니다.

시간복잡도

 시간 소요에 대한 척도

O(1) - 상수시간

• 입력 데이터의 크기와 상관없이 알고리즘의 실행 시간이 일정합니다. 

O(log n) - 로그시간

•  입력 데이터를 반으로 나눠 가며 문제를 해결 하는 알고리즘 (ex: 이진 탐색)입니다.
•  각 단계에서 입력 데이터의 크기가 절반으로 줄어들기 때문에 로그 시간 복잡도를 가진다.

O(n) - 선형시간

•  입력 데이터의 각 요소를 한번씩만 처리하는 알고리즘에서 나타납니다. 
•  예를 들어 배열의 모든 요소를 순회 하는 경우에 해당하빈다.

O(n log n) - 선형 로그 시간

•  대표 적으로 정렬 알고리즘 (ex: 퀵정렬, 병합정렬) 에서 볼 수 있습니다. 
• 여기서 n은 데이터를 처리하는 것, log n은 데이터를 나누는 것을 의미합니다.

O(n^2)

•  2개의 중첩 루프를 사용 하여 데이터 모든 쌍을 비교 하는 알고리즘 (ex: 버블 정렬 삽입 정렬) 에서 나타납니다.

공간복잡도

[...]

Big O 표기법의 단순화

1. 상수는 무시합니다.

•  O(5n+2)는 O(n)과 같습니다. 

2. 낮은 차수의 항목은 무시합니다.

•  O(n^2+n)은 O(n^2) 으로 단순화 합니다.

3. 로그의 베이스(밑)는 무시합니다.

•  로그의 베이스가 무엇이든 O(log n)으로 간주됩니다.
•  로그의 성장률은 베이스에 크게 의존하지 않기 때문입니다.

4. [...]

 n * log(n) [...]

O(n+n) vs O(n*n)

• Case1. O(n+n)
  • O(n)
• Case2. O(n*n) -
  • O(n^2)

알고리즘

특정한 문제를 해결하기 위한 명확한 명령의 집합으로서,

주어진 입력에 대하여 유한한 시간 내에 원하는 출력을 생성하는 절차

특정한 문제

•  데이터정렬, 초단경로 찾기, 문자열 검색하기

명확한 명령

•  알고리즘은 일련의 명령으로 구서오딥니다. 각 명령은 구체적이고 모호하지 않아야한다.

입력과 출력

•  Input  : 알고리즘은 0개 이상의 입력을 받을 수 있습니다.
•  Ouput : 하나 이상의 출력을 반환 합니다. 이 출력은 입력에 대한 해답이며, [...]

알고리즘을 제대로 학습하려면?

•  거의 모든 언어에 공통되는 연산만 사용하기
•  컴퓨터가 실제로 돌아가는 방법에 대해서 알아야한다. 

Memory 개념

• Code 영역 - Spring boot, java 표준 라이브러리 코드
• Data - static 변수, Singleton Beans
• Stack - 메소드 호출 정보, 지역 변수 등
• Heap - 동적 객체, Spring Beans, Entity 객체

실제로 애플리케이션에서 CPU가 메모리를 어떻게 사용 할까?

• 1. 요청 도착
  •  클라이언트로 부터의 요청이 웹서버에 도착하면, 서버는 요청을 처리하기 위한 쓰레드를 생성하거나 쓰레드 풀에서 쓰레드를 가져옵니다.
• 2. 스택 영역 활용
  •  요청을 처리하기 위한 쓰레드가 생성되면, 그 쓰레드는 스택 영역을 사용하여 메소드 호출 정보, 지역 변수 등을 관맇바니다. 
  • 서버는 요청 정보, 헤더 바디 등을 파싱하여 해당 정보를 메소드의 매개 변수나 지역 변수로 스택에 저장합니다.
• 3. Controller 맵핑 및 호출 
  •  스프링은 URL, HTTP 메소드 등을 기반으로 Controller 메소드를 찾습니다.
  •  해당 Controller 메소드이 바이트코드는 코드 영역에서 찾아져 CPU로 전달되어 실행됩니다.
• 4. 객체 생성 및 힙 영역 활용
  •  Controller 메소드 실행 중 필요한 객체
  •  [...] 
• 5. 데이터 영역 활용
  • [...]
• 6. 비지니스 로직 실행 및 DB 접근
  • [...]

2023.08.23