Imersive 시간복잡도(ver.기억의지속)

chltndid724·2019년 8월 1일
0

immersive

목록 보기
6/22
post-thumbnail

⌛ 시간복잡도(time complexity)

기본 개념

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

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

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

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

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

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

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

Big - O

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

profile
힘들땐 블로그 하나더 적자!!![ Suyang ]

0개의 댓글