Hello Coding 그림으로 개념을 이해하는 알고리즘 - 1장 요약

yesdoing·2018년 12월 9일
3
post-thumbnail

알고리즘이란?

  • 어떤 일을 하기 위한 명령의 집합

알고리즘 학습 시 중요한 것은 각 알고리즘들의 차이점을 이해하는 것.

  • 병렬 정렬 vs 퀵 정렬
  • 배열 vs 리스트

이진탐색

  • 입력: 정렬된 리스트
  • 출력: 리스트에 원하는 원소가 있으면 원소의 위치 반환 or null 반환

이진 탐색의 쉬운 예제

  • 1 ~ 100 중 원하는 숫자를 찾을 때 1, 2, 3, ..., 100 처럼 1씩 증가하면서 찾는 알고리즘은 Simple Search(단순 탐색)라고 한다.
  • 이진 탐색은 100의 중간 값인 50부터 검색을 시작한다.
  • 값 82를 찾는다고 하면 50 -> 75 -> 82 순으로 3번에 값을 찾는다.
  • 이진 탐색은 결과를 최대 log N 번만에 찾을 수 있다.

빅오 표기법

  • 알고리즘이 얼마나 빠른지 표시하는 특별한 방법
  • 속도를 시간 단위로 세지 않고, 연산 횟수를 비교하기 위한 것
  • 수행해야 할 일이 많아질 때, 알고리즘에 걸리는 시간이 어떤식으로 증가하는지 알수있다.(최악의 실행시간을 나타낸다.)
  • 이진탐색은 크기가 n인 리스트를 확인하기 위해 logN의 연산이 필요 (O(logN))
profile
Frontend Developer

0개의 댓글