JavaScript를 사용한 알고리즘 치트 시트

보통 부트 캠프에서 가르치지 않는 것. 관용적 JavaScript에서 일반적인 알고리즘의 실제 구현.

알고리즘에 대해 생각하는 방법, 알고리즘을 추정하는 방법, 최적화하는 방법, 재귀 및 신뢰할 수있는 JavaScript 엔지니어 로서 알아야하는 모든 사항을 소개합니다 . 인터뷰를 할 때 경력 초기에 알았 으면하는 것.

긴장을 풀고 시간을 갖고 즐기십시오.

알고리즘이란?

문제를 해결하기위한 일련의 지침입니다.
엔지니어로서 문제를 해결하는 것은 귀하의 직업 / 목표입니다.
문제를 해결할 때 더 효율적이고 성능이 좋은 패턴 / 기술을 식별합니다.
단일 문제를 해결하는 방법에는 여러 가지가 있지만 처리 할 입력 데이터의 양이 증가 할 때 가장 빠른 방법은 무엇입니까?

시간 복잡도 는 데이터가 제공 될 때 알고리즘에서 실행되는 기본 작업 수입니다.
알고리즘의 속도를 추론하는 데 도움이
됩니다. 입력 데이터가 증가함에 따라 알고리즘을 실행하는 데 걸리는 시간의 근사치입니다.
가능한 모든 유형에서 알고리즘을 실행하는 데 걸리는 시간을 정확히 예측할 수 없기 때문에 근사치입니다. 머신 아키텍처 / 환경 / 하드웨어 구성 등.
따라서 몇 초 또는 밀리 초를 사용하는 대신 데이터를 제공 할 때 알고리즘이 얼마나 증가하는 경향이 있는지를 나타내는 성장 인자가 사용됩니다.
요약하면 시간 복잡도하는 많은 방법입니다 기본 작업이 입력이 성장과에서 같은 문제를 해결하기 위해 실행되는 최악의 시나리오 .
수행 된 작업 비용 에 대해 생각해보십시오 . 알고리즘이 빠를수록 합리적인 시간에 더 많은 데이터를 처리 할 수 있습니다.

공간 복잡성 은 알고리즘을 실행할 때 입력 크기와 관련하여 사용되는 메모리 양입니다.

플랫폼에 VPN 제공 업체 목록이 있다고 가정 해 보겠습니다. 가장 비싸고 가장 저렴한 문제를 해결하려고합니다. 공급자는 매일 계속 추가되므로 목록이 계속 늘어나고 있습니다.

const vpnProviders = [
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 { name: 'tatoVpn', price: 99 },
 { name: 'tutoVpn', price: 54 },
 ...
];

목록을 반복하면서 반복 당 최고 및 최저 가격을 추적합니다.

가장 비싼 가격을 검색 할 때의 표현을 살펴 보겠습니다.

       |  234  |  321  |  99  |  54  |
--------------------------------------
  234  |  --   |  321  |  234 |  234 |
--------------------------------------
  321  |  321  |  --   |  321 |  321 |
--------------------------------------
   99  |  234  |  321  |  --  |  99  |
--------------------------------------
   54  |  234  |  321  |  99  |  --  |

 # of providers (n)  |   4  |  11  |  100     |  2000      |
------------------------------------------------------------
 # of operations     |  16  |  121 |  10,000  |  4,000,000 |

공급자 수가 n 개 증가하면 작업 수는 2의 제곱 (4², 11², 100² 작업)만큼 증가합니다.
따라서 기본적으로 데이터가 증가할수록 더 많은 작업이 필요합니다.

      |  234  |  321   |  ...  |  99  |  54  |
----------------------------------------------
max?  |  234  |  321   |  ...  |  321 |  321 |

      |  234  |  321   |  ...  |  99  |  54  |
- --------------------------------------------
min?  |  234   |  234  |  ...  |  99  |  54  |

목록의 각 항목은 루프 반복에서 한 번만보고 조건을 충족하면 저장됩니다 (최대 값, 최소값).
여기에서 시간 복잡도는 선형 ( 여기서는 2n)입니다. 모든 항목을 한 번 보는 두 개의 별개의 루프 때문입니다.
수행 할 작업 수는 항목 수의 두 배 또는 간단히 말하면 데이터가 증가함에 따라 작업이 2 씩 증가합니다.

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   8  |   22 |  200  |  4,000 |

const vpnProviders = [
 { name: 'tutoVpn', price: 54 },
 { name: 'tatoVpn', price: 99 },
 { name: 'totoVpn', price: 234 },
 { name: 'titoVpn', price: 321 },
 ...
];

루프가 필요없고, 두 번만 작동하고, 첫 번째 값을 최소값으로 설정하고 마지막 값을 최대 값으로 설정합니다.
따라서 알고리즘의 시간 복잡성은 항목의 수에 관계없이 작업 수가 동일하게 유지되기 때문에 지속적으로 증가 합니다.

# of providers (n)  |   4  |  11  |  100  |  2000  |
----------------------------------------------------
 # of operations    |   2 |    2  |    2  |   2    |

시간 복잡도 증가는 big O 표기법으로 표시됩니다.
지금까지, 우리는 보았다 :
- 이차 시간 복잡도는 로 표현 O (n²)
- 선형 시간 복잡도 로 표현 O (N)
- 상수 시간 복잡도는 로 표현 O (1)
tme 복잡도는 근사치이므로 중요하지 않은 숫자는 삭제되므로 2n의 시간 복잡도는 O (2n)이 아닌 O (n)입니다.
계수는 감소된다 :
- 5N은 O (N)은 [ "O (N)의"발음] 인
- 24n²가 O (n²)이다 "발음의 O N 사각형"]
다음은 성장을 그래픽으로 나타낸 것입니다.

x 축 = 데이터 입력, y 축 = 시간

시간 복잡성을 아는 것은 완료하는 데 백만 년이 걸리기 전에 얼마나 많은 데이터를 견딜 수 있는지에 대한 알고리즘의 한계를 이해하는 데 도움이됩니다.
또한 특정 조건에 따라 다른 알고리즘보다 하나의 알고리즘을 선택하는 것에 대한 절충안을 만드는 데 도움이됩니다.
알고리즘 정확성 의 개념은 알고리즘 선택에 관한 것입니다. 가장 최적 / 올바른 솔루션입니까?

A를 통지 로그 시간 복잡도 (O (로그 n)은) , 더 많은 데이터 당신이 처음에이 차 시간 복잡도보다 더 많은 시간이 소요되는 알고리즘은 상관이 덜하고 적은 작업뿐만 아니라 통지를 공급
그래서 매우 확대됨에 매우 느린에서, 당신이 :
- C onstant 시간 복잡도는 로 표현 O (1)
- L ogarithmic 시간 복잡도는 로 표현 O (로그 n)은
- 선형 시간 복잡도는 로 표현 O (N)
- 이차 시간 복잡성 으로 표시 O (n²)
- C UBIC 시간 복잡도 로 표시 O (n³)
- 지수 시간 복잡도 로 표시 O (K)