[TIL][알고리즘 기초] Complexity | Deep / Shallow Copy

Complexity

Big-oh Notation시간 복잡도에 대해 설명해주세요.

O() 로 표기되는 빅 오 표기법은 최악의 경우에서의 성능을 나타냅니다.

시간/공간복잡도에 대해 설명해주세요.

알고리즘이 얼마나 효율적인지 판단하는 척도입니다. 각각 특정 크기의 입력(n)을 기준으로 연산 시간 또는 메모리 사용량이 얼마나 되는지 객관적으로 판단하는 데 쓰입니다. 두 복잡도 모두 빅오 표기법을 사용하여 표현할 수 있습니다. O() 로 표기되는 빅 오 표기법은 최악의 경우에서의 성능을 나타냅니다. 시간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 시간의 양을 의미하고, 입력된 데이터의 크기와 실행 시간 간의 비례 관계를 나타내는 지표입니다. 공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리의 양을 나타냅니다. 입력한 데이터의 처리 과정에서 필요한 저장 공간으로 결정됩니다.

시간 복잡도와 관련된 요소에 대해 설명해주세요.

상수 시간(O(1))

• 입력 데이터의 크기에 상관 없이 일정한 시간이 소모됩니다.일반적인 stack/queue의 삽입/인출이 해당됩니다.

로그 시간(O(log n))

• 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아집니다.이중 탐색 알고리즘, 혹은 tree형태의 자료구조 탐색 등이 이에 해당됩니다.

선형 시간(O(n))

• 입력 데이터의 크기에 비례해 처리 시간이 길어집니다. 1차원 for문이 해당됩니다.

선형 로그 시간(O(n log n))

• 입력 데이터의 크기에 비례헤 처리 시간이 로그만큼 길어집니다. 병합 정렬, 퀵 정렬, 힙 정렬이 이에 해당됩니다.

2차/3차 시간(O(n^2) / O(n^3))

• 입력 데이터의 크기에 비례해 처리 시간이 급수적으로 늘어납니다. 이중 for문 혹은 삽입 정렬, 버블 정렬, 선택 정렬이 해당됩니다.

공간 복잡도와 관련된 요소

• 변수
• 자료 구조
• 함수 호출
• 할당

시간 복잡도는 매우 낮지만 메모리를 매우 많이 사용한다면 어떻게 대처할 수 있을까요?

(시간 복잡도가 낮다는 뜻은 알고리즘이 시간 측면에서는 효율적이란 뜻이지만, 메모리를 많이 사용한다면 다른 대안을 생각해 볼 수 있습니다.) 현재 사용 중인 자료구조/데이터 구조를 메모리를 덜 사용하는 방향으로 구현해볼 수 있습니다.

• 그러나 보통 시간 복잡도와 공간 복잡도, 즉 시간과 메모리자원(공간)은 반비례적인 경향이 있습니다.

ref

기술 면접에서 시간 복잡도를 물어보는 이유 & 매우 간단한 시간복잡도 문제 소개 

시간 복잡도: 위키

Deep / Shallow Copy

깊은 복사와 얕은 복사에 대해 설명해주세요.

객체의 얕은 복사는 객체의 참조값을 복사합니다.(사본의 속성이 원본 객체와 같은 참조를 공유) 이 경우 원본이나 복사본을 변경할 경우, 복사본이나 원본이 함께 변경됩니다. 이런 경우를 피하려면 깊은 복사가 필요합니다. 반대로 깊은 복사는 객체의 값을 복사합니다.(사본의 속성이 원본 객체와 다른 참조를 가지는 복사, 비공유) 따라서 원본/사본 복사시 상대편 객체가 변경되지 않습니다.

ref

mdn: shallow copy mdn: deep copy