⌛ 시간복잡도(time complexity)

기본 개념

실행시간은 실행 환경에 따라 다릅니다.(하드웨어, 운영체제, 언어, 컴파일러 등)
실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 합니다.
연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현합니다.
데이터 크기가 같더라도 실제 데이터에 따라서 달라집니다.

최악의 경우 시간복잡도(worst -case analysis)
평균 시간 복잡도 (average - case analysis)

  • n ^ 2 ( 2차 시간: 문제를 해결하기 위한 단계의 수와 입력값 n의 제곱)

스크린샷, 2019-08-02 02-03-59.png

  • 2 * n ( 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값이 1 : 1 관계를 가짐 )

스크린샷, 2019-08-02 01-31-00.png

다섯개의 요소를 찾기위해 2 * 5 = 10 즉, 열번을 돌아야지 찾을수 있다.

  • 1 (constant Time = Awesome)
  • (상수시간 : 입력값 n이 주어졌을때, 알고리즘이 문제를 해결하는데 오직 한단계만을 거침)

정렬 되있다는 가정하에 맨앞과 맨뒤에 값을 빼므로 1번만에 되기에 제일 빠르다 할 수 있다.

스크린샷, 2019-08-02 01-34-03.png

Big - O

위에 첫번째 꺼는 n^2 => O(n^2)
두번째 꺼는 2n => O(n)
세번째 꺼는 1 => O

스크린샷, 2019-08-02 01-58-35.png

스크린샷, 2019-08-02 01-58-54.png