기술 면접 스터디 - 8회차 ( 시간 복잡도와 공간복잡도, 오버라이딩, 오버로딩)

목차

• 1. 시간복잡도와 공간복잡도란? 중요성까지
• 2. 오버라이딩과 오버로딩의 차이점

1. 시간복잡도와 공간복잡도란? 중요성까지

 

복잡도라는 개념은 성능에 대한 평가의 척도입니다.

그래서 시간 복잡도 같은 경우엔 말 그대로 얼마나 수행하는지, 즉 시간의 관점에서 표기하는 방법이고, 공간 복잡도는 얼마나 메모리 공간을 사용하는지 즉 물리적인 관점에서 보는 방법입니다.

 

1. 시간 복잡도( Time Complexity )

시간복잡도는 실행 환경에 따라 다르게 측정되기에 연산의 실행 횟수로 수행 시간을 평가합니다. 

시간복잡도는 3가지 case로 나타냅니다

• 1. 최선의 경우 (Best Case)
  • 최선의 경우엔 빅 오메가 표기법을 사용하고, 최선의 시나리오를 의미합니다. ( 가장 좋은 케이스 )
• 2. 최악의 경우 (Worst Case)
  • 빅 오 표기법을 사용하고, 최악의 시나리오를 의미합니다. ( 가장 안좋은 케이스)
• 3. 평균적인 경우 (Average Case)
  • 빅 세터 표기법을 사용하고, 평균적인 시간을 나타냅니다.

복잡도는 알고리즘이 복잡해질수록 평균을 구하기 힘들기에 최악의 경우로 알고리즘의 성능을 파악합니다.

 

https://www.bigocheatsheet.com/

 O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)

1. O(1) : 상수 시간 ( Constant time ) : 입력 크기 n에 상관없이 일정한 연산을 수행

2. O(logN) : 로그 시간 ( Logarithmic time ) : 입력 크기 n이 커지면, 연산 횟수 logN도 비례해서 커집니다. 

3. O(N) : 선형 시간 ( Linear time ) : 입력 크기 n이 커지면 연산횟수 n에 비례해 같이 커집니다.

4. O(N^2) : 2차 시간 ( Quadratic time) :  입력 크기 n이 커지면 n^2에 비례해 커집니다.   ( 2중 for문 )

5. O(2^n) : 지수 시간 ( Exponentital time) :  입력크기 n이 커지면 2^n에 비례해 커진다  ( 재귀 호출 )

 

위 관계에서 복잡도는 오른쪽으로 갈 수록 복잡도가 큰 알고리즘입니다.

이말은 수행 시간이 긴 알고리즘입니다. 시간 복잡도를 낮출 수 있다면 프로그램의 성능 향상에 큰 기여를 할 수 있습니다. 

 

2. 공간 복잡도 ( Space Complexity )

공간 복잡도는 빅오 표기법을 사용하며 알고리즘에 사용되는 메모리 공간의 총량입니다.

 

사실상 하드웨어가 많이 발전하고 공간 복잡도의 중요성은 많이 낮아졌습니다. 앞서 복잡도라는 개념은 결국 성능을 측정하는 척도라고 언급했는데, 데이터의 양이 많아질수록 복잡도는 증가할 수 밖에 없습니다. 그래서 복잡도를 어떻게하면 낮출 수 있을까?에 관한 고민이 결국 성능과 직결되기에 중요하다 생각합니다.

---

2. 오버라이딩과 오버로딩의 차이점

오버라이딩의 정의는 상위 클래스 (부모 클래스)에서 상속받은 메서드를 하위 클래스(자식 클래스)에서 재정의해서 사용함을 의미하고 있습니다.

오버로딩은 같은 이름을 가진 메소드를 매개변수의 갯수나, 메소드의 리턴값, 타입 값이 다르면 다른 메소드로 취급함을 의미하고 있습니다. 

 

어떻게보면 공통점이라고 하면 객체지향의 특징인 다형성의 성질을 이용할 수 있다는 점에서 공통점이 있습니다. 그러나 오버라이딩은 부모 클래스의 메서드를 상속받아서 사용하기에 매개변수나, 타입이 동일해야하지만 오버로딩은 다르게 구현해야 합니다.

또한 오버 라이딩 같은 경우엔 리턴 타입이 동일해야 하지만, 오버로딩은 상관없습니다.