큰 O, 곤혹스러운 것

의심할 여지없이 Time Complexity은 네가 처음으로 컴퓨터 과학 분야에서 방향을 찾았을 때 가장 이해하기 어려운 화제 중의 하나이다.내가 여기 온 것은 그 곤혹스러운 부분을 간단하게 하기 위해서이다.구체적으로 말하면, 지수, 2차, 대수 시간의 복잡성에 관해서는, 당신은 여전히 어떠한 곤혹스러움도 존재할 수 있습니다.
그러나 우리가 깊이 연구하기 전에 간단한 것에 만족한다는 것을 확신합시다.
간단하게 말하면 시간 복잡도는 프로그램의 효율을 분석하는 도구로 프로그램의 규모와 관련이 있다.낮은 시간의 복잡도는 항상 더 빠른 프로그램을 초래할 수 있고, 더 높은 복잡도는 항상 비교적 느린 프로그램을 초래할 수 있다.
상수와 선형의 복잡성은 대O 표현법으로 -O(1) && O(n)타인을 존중하고 자신을 이해하기 쉽다.입력한 크기와 상관없이 일정한 시간 복잡도는 같은 시간을 필요로 하기 때문에 우리는 그것을 '1' 이라고 표시한다.
선형 축소 프로그램의 시간 복잡도는 항상 입력의 크기와 직결된다. 위와 같이 n이다.
배열의 길이가 중요하지 않기 때문에, 배열이 항상 고정되어 있습니다.

let arr = ["one", "two", "three"];
arr.pop() ---> "three"

같은 수조에서 순환은 항상 선형적이다. 왜냐하면 우리가 조작하는 길이는 수조의 길이와 직접적으로 관련이 있기 때문이다.

for(let i = 0; i < arr.length; i++)

"n"을 배열 자체의 길이로 바꾸면 개념화에 도움이 될 수 있습니다.기술적으로 볼 때'arr'수조에서 순환하는 시간의 복잡도는 O(3)가 팝업 포트 앞에 있고 O(2)가 팝업 포트 뒤에 있다.
그러나 이것은 매우 간단한 일이다. 나는 여기서 사람을 곤혹스럽게 하는 부분을 명확하게 밝혔다.자, 시작합시다.
지수형

우리가 exponential의 시간의 복잡성을 이야기하기 전에, 우리는 우선 이 단어 자체의 뜻을 이해하도록 노력해야 한다'지수' 는 '성장이 갈수록 빨라지는 것' 을 가리킨다.
또 다른 견해는 이것이 끊임없이 증가하는 성장이라는 것이다.우리는 지수 시간의 복잡도를O(2^n)이 중 n은 입력 크기입니다.
상상할 수 있는 바와 같이, 프로그램이 지수급의 시간을 들여 그 조작을 완성하는 것은 대부분의 용례에서 절대적인 재난일 수 있으며, 특히 대형 데이터 집합을 처리할 때이다.
예를 들어 시간 복잡도가 지수인 함수 범람 길이가 20인 그룹이 있다면 O(2^n)를 작성하고 해결 방안을 분석함으로써 실행해야 할 잠재적 최대 동작을 계산할 수 있다.

   2 ^ 20 = 1,048,576

이것은 절대적으로 최악의 상황에서 우리의 지수 함수의 시간 복잡도는 O(1048576)라는 것을 의미한다.
나는 아래에 우리가 허구한 프로그램의 시간 복잡도가 어떻게 수조의 크기에 따라 20만 위안으로 확장되는지 열거했다.이것은 나날이 증가하는 성장이 실제로 무엇을 의미하는지 상상하는 데 도움이 될 것이다.
오른쪽의 숫자를 따라가서 네가 무엇을 알아차렸는지 봐라.

2 ^ 1 = 2
2 ^ 2 = 4
2 ^ 3 = 8
2 ^ 4 = 16
2 ^ 5 = 32
2 ^ 6 = 64
2 ^ 7 = 128
2 ^ 8 = 256
2 ^ 9 = 512
2 ^ 10 = 1,024
2 ^ 11 = 2,048
2 ^ 12 = 4,096
2 ^ 13 = 8,192
2 ^ 14 = 16,384
2 ^ 15 = 32,768
2 ^ 16 = 65,536
2 ^ 17 = 131,072
2 ^ 18 = 262,144
2 ^ 19 = 524,288
2 ^ 20 = 1,048,576

길이가 늘어나면서 시간의 복잡도가 배가되었다.
이것은 우선 안정적인 성장을 취하고 9단계로 1000을 돌파한 다음에 5단계로 10000을 돌파하는 것이다.그러나 네 발자국 떨어진 곳에서만 수십만 명을 늘릴 수 있고, 두 발자국만 지나면 우리는 백만 명에 이른다.2^18과 2^20의 차이는 이전의 모든 결과의 총계보다 크다.
지수의 복잡도에 대해 가장 흔히 볼 수 있는 실용 예는 fibonacci number을 가져오는 함수입니다.

let fibonacci = function(number) {
  if (number <= 1) {
    return number;
  }
  return fibonacci(number - 2) + fibonacci(number - 1);
};

입력이 클수록 피보나 계수를 출력하는 데 필요한 연산이 많아진다.비귀속 버전을 직접 만들 수 있는지 시험해 보세요.알잖아, 그냥 재미로 하는 거야.
2차(다항식)

다시 한 번 시간과 복잡도의 관계를 먼저 이해하기 위해 quadratic의 정확한 의미를 보여 드리겠습니다.간단하게 말하면 이것은 기이한 단어로 수학자가 그것을 이용하여 어떤 물건의 제곱을 나타낸다. 이것이 바로 우리가 그것을 -O(n^2)아주 간단하죠?2차 함수 중 가장 큰 연산 횟수는 입력 시간 자체의 길이다.
예를 들면 다음과 같습니다.

let repeatArrayByLength = function(arr){
let newArr = [];
for(let i = 1; i <= arr.length; i++){
  for(let j = 1; j <= arr.length; j++){
    newArr.push(j);
  }
}
return newArr;
};

2차 축소는 입력 길이가 증가함에 따라 함수가 완성해야 하는 프로세스 수량이 증가하고 수조 길이가 자신의 인자인 n^2을 곱하기 때문이다.
다음 그림과 같이 길이 3의 배열을 가져오는 경우 주의하십시오.repeatArrayByLength([1, 2, 3])저희가 돌아올게요 -[1, 2, 3, 1, 2, 3, 1, 2, 3]우리의 함수는 3의 입력 길이에서 수조로 9차례 전송되었다.3^2 또는 3 * 3은 9입니다.
만약 우리가 길이가 5인 유사한 구조의 그룹을 전송한다면, 우리는 되돌아갈 것이다.[1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]우리의 함수는 수조 25번에 밀려들었다.5^2 또는 5 * 5은 25입니다.
대수적

나는 logarithmic의 시간 복잡성을 지수 복잡성의 합리적인 버전으로 상상하고 큰 O로 -O(log n)지수 함수의 연산 횟수는 입력의 크기에 따라 증가하고 대수 함수의 연산 횟수는 입력의 크기에 따라 감소한다.데이터 세트가 클수록 프로그램 실행의 효율이 높아진다.
다음은 간단한 예입니다.

let doubleStepper = (number) => {
  let arr = [];
  for (let i = 1; i < number; i *= 2) {
    arr.push(i);
  }
  return arr;
};

5을 통과하면 다음과 같이 돌아갑니다.[1, 2, 4]
세 번밖에 안 움직였어.이제 100을 통과하면 다음과 같이 돌아갑니다.[1, 2, 4, 8, 16, 32, 64]일곱 번밖에 안 움직였어.입력 데이터가 증가함에 따라 대수의 복잡도를 가진 함수는 지수 형식으로 더욱 효율적으로 변할 것이다.
마지막으로 우리는 미친 듯이 5000을 통해 돌아온다.[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,4096]이것은 결코 매우 큰 도약이 아니다. 모두 13개의 프로세스만 있다.앞서 말씀드린 바와 같이 입력 크기가 증가함에 따라 그것의 효율도 점점 높아질 것입니다.1과 32의 점프는 1024과 4096의 점프보다 많다.
나는 그것이 지수의 합법적이고 좋은 버전이라고 농담한 것이 아니다. 다음은 증거이다.

그것들은 같은 곡선을 가지고 있지만 방향이 다르다.
일반적으로 우리는 프로그램의 복잡도를 상수, 대수, 또는 최소 선형을 목표로 하지 않고 지수와 2차 복잡도 이하로 제어하려고 노력해야 한다.
마찬가지로 가장 나쁜 상황에만 따라 시간의 복잡도를 정해야 한다는 것을 명심해야 한다.왜냐하면 이런 터무니없는 함수라도-

- 이론적으로 bogosort은 첫 번째 배열에서 정확한 결과를 얻을 수 있다.그러나 그것을 변하지 않게 할 수는 없다. 사실은 그렇지 않다.상술한 함수는 실제로 factorial의 시간 복잡도를 가지고 있는데 이것은 또 다른 토론이다.