Topic

Search/Sort algorithm
Big O notation
Time/Space complexity

What I Learned

1. 알고리즘이란?

• 알고리즘(algorithm) 유한하게 연속적인 정밀한 명령
• 문제를 효율적이게 해결하는 것이 좋은 알고리즘이다.

2. 탐색, 정렬 알고리즘

탐색 알고리즘

• 탐색(Search): 저장된 정보들 중에서 원하는 값을 찾는 것
• 선형 탐색 알고리즘(linear search algorithm)
  • 한쪽 끝에서 시작하여 원하는 요소를 찾을 때까지 목록의 각 요소를 검색하는 알고리즘
  • Performance
    • Worst-case time complexity: O(n)
    • Best-case time complexity: O(1)
    • Average time complexity: O(n)
    • Worst-case space complexity: O(1)
    • Best-case space complexity: O(1)
    • Average space complexity: O(1)
• 이진 탐색 알고리즘(binary search algorithm)
  • 정렬된 배열에서 탐색 범위를 절반씩 줄여 나가면서 원하는 요소를 찾는 알고리즘
  • Process
    1. 정렬된 배열에서 원하는 요소와 배열의 중간 요소를 비교합니다.
    2. 동일하지 않으면 대상이 존재할 수 없는 배열의 절반이 제거되고 나머지 배열 절반에서 검색이 계속됩니다.
    3. 반으로 줄어든 배열에서 대상 값을 찾을 때까지 이 작업을 반복합니다.
  • Performance
    • Worst-case time complexity: O(log n)
    • Best-case time complexity: O(1)
    • Average time complexity: O(log n)
    • Worst-case Space complexity: O(1)
    • Best-case Space complexity: O(1)
    • Average Space complexity: O(1)

2. 정렬 알고리즘

• 정렬(Sorting): 배열의 요소들을 특정 순서로 정리하는 것
• 선택 정렬(Selection Sort)
  • Process
    1. 주어진 배열의 요소 중 최솟값을 찾습니다.
    2. 그 값을 맨 앞에 위치한 값과 교체합니다.
    3. 맨 처음 위치를 제외한 나머지 배열에서 같은 방법을 반복합니다.
  • Performance
    • Worst-case time complexity: O(n^2)
    • Best-case time complexity: O(n^2)
    • Average time complexity: O(n^2)
    • Worst-case Space complexity: O(1)
    • Best-case Space complexity: O(1)
    • Average Space complexity: O(1)
• 삽입 정렬(Insertion Sort)
  • Process
    1. 배열의 두 번째 요소부터 시작합니다. (첫 번째 요소는 정렬이 되어있는 상태이기 때문에)
    2. 그 요소의 왼쪽에 위치한 부분 배열과 비교하여, 그 요소를 부분 배열 속에 삽입할 위치로 이동시킵니다.
    3. 나머지 배열에서 같은 방법을 인덱스 순서대로 반복합니다.
  • Performance
    • Worst-case time complexity: O(n^2)
    • Best-case time complexity: O(n)
    • Average time complexity: O(n^2)
    • Worst-case Space complexity: O(1)
    • Best-case Space complexity: O(1)
    • Average Space complexity: O(1)

알고리즘 평가법

점근 표기법(Big-O notation)이란?

• Argument가 특정 값이나 무한대로 향하는 경향이 있을 때, 함수의 동작 범위를 설명하는 수학적 표기법
• Formal definition
  - f(x) 평가할 함수
  • g(x) 충분히 큰 모든 x 값에 대해서 strictly positive한 비교 함수
  • 다음을 만족하는 양의 실수 M, 실수 x0가 존재할 때, f(x) = O(g(x))라고 한다.
    • |f(x)| <= Mg(x) for all x >= x0
    • x가 무한대로 향하는게 아닌, 특정 값으로 향할 때에도 비슷하게 정의한다.
      • Big O notation 참조
    • f(x) = O(g(x))에서 등호는 일반적인 의미가 아니므로, 교환 법칙이 성립하지 않는다

2. 시간, 공간 복잡도
   • 시간복잡도와 공간복잡도 참조
3. Python operaions complexity
   • O(1)
     • len(my_list)
     • my_list.append(element)
     • my_list[index]
     • type(data)
     • len(my_list)
     • my_dict[key]
     • my_dict[key] = value
     • del my_dict[key]
   • O(n)
     • my_list.insert(index, element)
     • del my_list[index]
     • my_list.reverse()
     • element in my_list
     • min(my_list)
     • max(my_list)
   • O(log n)
     • str(my_number)
   • O(n * log n)
     • my_list.sort()
     • sorted(my_list)
   • O(b - a)
     • my_list[a:b]

Feedback

• 자바스크립트 내장 함수들의 소스 코드로 알고리즘 분석하자.
• 자바스크립트 모듈에 대해 공부하자.
• 다음으로 '알고리즘 패러다임' 코드잇 콘텐츠를 수강할 예정이다
  
  
• 파이썬이 아니라 자바스크립트 operations complexity를 찾아보자.

Reference

• Algorithm - Wikipedia
• Big O notation - Wikipedia
• 좋은 알고리즘이란? - 알고리즘 · 자료구조 강의 | 코드잇