이번 포스팅에서는 시간 복잡도에 대해서 알아보겠습니다.

1. 시간복잡도란(Time Complexity)

정의

: 컴퓨터과학 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.

  • 시간 복잡도를 이용하면 작성한 코드가 시간이 대략 얼마나 걸릴지 예상할 수 있다.
  • 표기법으로는 대문자 O를 사용한다.(영어로는 Big O Notation)
  • 입력 값 크기(N)에 대해서 시간이 얼마나 걸리는지 나타내는 방법
  • 즉, 최선의 경우, 중간의 경우, 최악의 경우에 시간이 얼마나 걸리는지도 알 수 있다.

2. 시간복잡도의 종류

종류

  • 1초가 걸리는 입력의 크기
  • O(1): 1초
  • O(N): 1억
  • O(log N)
  • O(N^2): 1만

  • Big O Notation에서 상수는 버리고 시간 복잡도를 계산한다

    (예시) - O(5) = O(1)
    - O(2N^2) = O(N^2)

예시

시간복잡도 O(1)

  • 1부터 N까지의 합을 계산하는 코드

시간복잡도 O(N)

  • 1부터 N까지의 합을 계산하는 코드

시간복잡도 O(N^2)

  • 1부터 N까지의 합을 계산하는 코드

참고

C# 배열 합치기

1.Concat arr1.Concat(arr2)는 arr1 배열과 arr2 배열을 하나로 병합하고 enumerable 객체로 return합니다. ToArray()로 Eumerable을 배열로 변환할 수 있다. 합쳐진 요소들이 Enumerable로 return되기 때문에, ...

C# 배열

개념 여러 값을 저장할 수 있는 자료 구조 배열은 단일 차원, 다차원 또는 가변일 수 있다. 차원 수는 배열 변수를 선언할 때 설정된다.

C# 반복문(while)

개념 조건식이 true일 때 동안 계속해서 반복하여 코드를 실행한다. 반복하다 조건식이 false가 되면 루프(반복되는 부분)를 빠져나옴. 하지만 조건식이 계속 true라면 루프(반복되는 부분)를 빠져나오지 못하고 계속 반복되는 무한루프에 빠지게 된다.

C# 반복문(for, foreach)

개념 C#에서 for와 foreach를 비교하는 것은 흔히 성능적 측면과 코드 가독성 측면을 고려하는데, 성능적 측면은 for가 경우에 따라 더 빠를 수 있지만 대부분의 경우는 성능적 차이는 크지 않으며 foreach는 for보다 훨씬 간결한 코드를 제공한다는 장점을 가지고 ...