JavaScript의 시간 복잡도 분석 - Lee-hyuna/33-js-concepts-kr GitHub Wiki

알고리즘은 문제를 해결하기 위한 독립적인 단계별 지침입니다.
이 단계를 완료하는 데 시간이 걸립니다. 알고리즘이 문제를 해결하는 데 걸리는 시간을 시 복잡성이라고 합니다.

시간복잡성의 공식적인 정의는 다음과 같습니다.
알고리즘의 시간복잡성은 알고리즘이 입력을 나타내는 문자열 길이를 함수로 실행하는 데 걸리는 시간을 정량화 한 것입니다.

이것은 입이 꽉 찬 것처럼 들리는데 당신은 아마도 그것이 무엇을 의미하는지 정확히 이해하기 위해 노력하고 있을 것이다.
간단히 말해서, 시간 복잡성은 특정 알고리즘이 요구하는 시간과 공간에 의해 정의됩니다.

문제를 해결하는데 사용할 수 있는 다양한 방법을 찾는 것은 드문 일이 아닙니다.
소요 시간과 수행 된 작업 수는 알고리즘이 문제를 해결하는데 얼마나 효과적인지 결정하는 데 사용됩니다.
복잡성은 프로그래머가 코드의 효율성을 이해하고 향상시키는데 도움이됩니다.

JavaScript에서 최고의 프로그래밍 솔루션은 가능한 가장 작은 시간 복잡성을 제공하는 알고리즘을 사용합니다.

큰 O 표기법

알고리즘의 시간 복잡도는 일반적으로 큰 O 표기법을 사용하여 표현됩니다.
큰 O 표기법은 알고리즘에 필요한 실행 시간 또는 간격을 설명합니다. 큰 O 표기법은 특히 최악의 시나리오를 설명합니다.

앞서 알고리즘에서 언급했듯이 문제를 해결하기위한 단계별 지침이 있습니다.
문제가 클수록 알고리즘이 문제를 해결하는데 더 오래 걸릴 것으로 예상합니다.

문제의 규모가 커짐에 따라 비용이 빠르게, 느리게 또는 간신히 증가 할 수 있습니다.
큰 O 표기법은 솔루션이 얼마나 빨리 문제를 해결하는지 측정하는데 사용됩니다.

다음 도표는 큰 O 표기법의 다양한 레벨과 조작 및 요소 수에 따라 완료하는 데 걸리는 시간을 보여줍니다.

다음은 일반적인 성장 순서와 해당큰 O 표기법 값입니다.

O (1) – 일정 시간 복잡성

큰 O 표기법 스케일에서 가장 빠른 시간 복잡성을 상수 시간 복잡성이라고합니다. 값은 O(1)입니다.

일정한 시간의 복잡성으로 인해 입력의 크기에 상관없이 계산하는 데 항상 같은 시간이 걸립니다.

일정한 시간은 JavaScript 함수에 대한 최상의 시나리오로 간주됩니다.
예 : 배열 조회, 해시 테이블 삽입

O(log n) – 대수

로그 표기법을 사용하면 실행 시간이 증가하지만 속도는 감소합니다.

다음은 로그 검색을 보는 방법에 대한 좋은 예입니다. 전화번호부에서 백만 개의 이름을 가진 사람을 찾고 싶습니다.

첫 번째 단계는 중간 지점 인 500,000개의 항목을 찾아서 검색하는 이름과 비교하는 것입니다.
알파벳에서 중간 점 이름이 사용자 이름보다 낮으면 이 프로세스를 반복하되 상위 500,000개의 이름만 사용하십시오.

이 500,000개의 이름의 중간 점을 찾아 이를 대상 이름과 비교하십시오.
중간 점 이름이 위 또는 아래이면 이름의 상위 절반 또는 하위 절반 만 사용하여 이 프로세스를 반복하십시오.

전화 번호부에 이름이 세 개만 있으면 대상 이름을 찾기 위해 최대 2번의 조회를 수행해야합니다.

전화 번호부에 15개의 이름이 있으면 대상 이름을 찾는 데 최대 4번의 조회가 필요합니다.

전화 번호부에 백만개의 이름이 있으면 대상 이름을 찾기 위해 최대 20번의 조회만 하면 됩니다.

보시다시피 완료 시간은 증가하지만 입력 크기가 증가하는 것만 큼 빠르지는 않습니다.

예 : 이진 검색

O(n) – 선형

O(n)은 성능이 입력 데이터 세트의 크기에 비례하여 선형적으로 증가하는 알고리즘을 설명합니다.

10개의 요소가 있는 배열의 내용을 인쇄 한다고 가정해 봅시다. 각 요소를 인쇄하는 배열을 반복합니다.

배열에 100개의 요소가 있는 경우 모든 항목을 인쇄하기 위해 루프를 100회 반복합니다.

백만개의 요소를 사용하면 백만번의 반복이 필요합니다.

보시다시피 크기가 증가함에 따라 시간 복잡성이 증가하고 동일한 속도로 증가합니다.

예 : 배열의 요소 인쇄

O(n^2) – 2차

2차 시간 복잡도는 거의 로그 복잡도의 역수입니다. 2차 복잡성으로 실행 시간이 증가하는 속도로 증가합니다.

2차 시간은 함수의 실행 시간이 입력 크기의 제곱에 비례 함을 나타냅니다.
2차 시간은 일반적으로 '차수 N 제곱'또는 O(n^2)로 표시됩니다.
2차 시간 복잡성으로 인해 일반적으로 O(1) 또는 O(n) 인 두 개의 연산을 자체적으로 완료하기 때문에 이 표기법이 사용됩니다.

예 : 두 개의 중첩 된 for- 루프 내에서 상수 시간 연산, 두 정수 목록을 서로 비교하고 버블 정렬을 비교합니다.