빅오 표기법

빅오 표기법 예시

• O(1) - 상수 시간: 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정
  • ex) 배열에서 인덱스를 사용하는 경우
• O(n) - 선형 시간: 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가
  • ex) 배열의 검색, 배열의 모든 요소를 순회하는 경우
• O(n²) - 제곱 시간: 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가
  • ex) 보통 이중 루프를 사용하는 알고리즘에서 나타남
• O(log n) - 로그 시간: 알고리즘의 실행 시간이 데이터 크기의 로그에 비레하여 증가
  • ex) 이진 탐색
• O(n log n) - 선형 로그 시간
  • ex) 많은 효율적인 정렬 알고리즘들

빅오 표기법은 매우 큰 데이터가 들어왔을 때 대략적인 추세를 비교하기 위한 것이 목적

보통 최악의 상황을 가정해서 표기

• 최적의 경우: 배열의 첫번째 항목에서 바로 값을 찾으면 O(1)
• 최악의 경우: 마지막 항목에 있거나 항목이 없는 경우 전체 요소 순회 O(n)
• 평균의 경우: 평균적으로 보통 중간쯤 데이터를 발견 함. 이 경우 O(n/2)가 되지만, 상수를 제외해서 O(n)으로 표기

참고

• https://www.inflearn.com/course/김영한의-실전-자바-중급-2