번역 : https://www.freecodecamp.org/news/time-is-complex-but-priceless-f0abd015063c/

모든 훌륭한 개발자는 시간에 중요시 합니다. 그들은 사용자에게 더 많은 것을 제공하기를 원하므로 사용자의 즐거움에 관해서 무엇이든 할 수 있습니다. 시간 복잡성을 최소화하여 이를 수행합니다.

당신이 시간복잡도를 이해하기 전에 어디서 대게 적용이 되는지 이해해야 한다. : 알고리즘 디자인 에서 적용이 된다.

그래서 알고리즘이 무엇이냐 간단하게 알고리즘은 절차를 포함하고 있는 단계이다. 이것은 한 목표를 달성 또는 결과물을 만들어내기 위한 단계 입니다. 다음 할머니의 케잌을 만드는 레시피를 살펴 봅시다. 잠깐, 여기서 몇개의 알고리즘이 사용되었는지 확인해 보자.

function BakeCake(flavor, icing){
"
 1. Heat Oven to 350 F
 2. Mix flour, baking powder, salt
 3. Beat butter and sugar until fluffy
 4. Add eggs.
 5. Mix in flour, baking powder, salt
 6. Add milk and " + flavor + "
 7. Mix further
 8. Put in pan
 9. Bake for 30 minutes
10." + if(icing === true) return 'add icing' + "
10. Stuff your face
"
}

BakeCake('vanilla', true) => deliciousness

알고리즘은 시간복잡도를 시험하기에 유용합니다. 왜냐하면 알고리즘들은 모든 모양과 크기를 나타낼수 있기 때문이다.

같은 방식으로 파이를 조각낼수 있는 방법이 100가지가 있다고 했을때, 당신은 다른 여러가지 알고리즘에서 한가지로 이 문제를 해결 할 수 있습니다. 몇몇 해결책들은 효율적이고 시간이 덜 들면서 다른것보다 더 적은 공간을 요구합니다.

그래서 주된 질문은 어떻게 우리가 해결책이 가장 효율적인지 분석을 하는가에 대한 것이다.

수학이 해결해줄것이다! 프로그래밍의 시간 복잡도 분석은 주어진 입력 수 (n)를 가진 알고리즘이 작업을 완료하는 데 걸리는 시간을 분석하는 매우 단순화 된 수학적 방법입니다. 이는 대게 Big-O 표기법을 사용해서 정의한다.

Big-O 표기법은 알고리즘의 전체 단계를 대수용어로 바꾸는 방법입니다. 그 후에 문제의 전체 복잡성에 큰 영향을 미치지 않는 하위 상수 및 계수를 제외합니다.

수학자들은 아마도 내 "전반적인 영향" 가정에 대해 약간의 비난을 할 것이지만 개발자가 시간을 절약하기 위해 다음과 같은 방식으로 일을 단순화하는 것이 더 쉽습니다.

Regular       Big-O

2             O(1)   --> It's just a constant number

2n + 10       O(n)   --> n has the largest effect

5n^2          O(n^2) --> n^2 has the largest effect

간단히 말해서,이 모든 예는 다음과 같습니다. 우리는 표현이 반환 할 가치에 가장 큰 영향을 미칠 수있는 표현의 요소만을 봅니다. (상수가 클수록 n이 작아 지지만, 지금은 걱정하지 않아도됩니다.)

다음은 간단한 정의로 인한 일반적인 시간 복잡도입니다. 보다 자세한 정의는 Wikipedia를 확인하십시오.

• O (1) — 상수 시간 : 크기 n의 입력이 주어지면 알고리즘이 작업을 수행하는 데 단 한 단계 만 걸립니다.
• O (log n) — 로그 시간 : 크기 n의 입력이 주어지면 작업을 수행하는 데 걸리는 단계 수가 각 단계마다 일부 요인으로 줄어 듭니다.
• O (n) — 선형 시간 : 크기 n의 입력이 주어지면 필요한 단계 수는 직접 관련됩니다 (1-1).
• O (n²) — 2 차 시간 : 크기 n의 입력이 주어지면 작업을 수행하는 데 걸리는 단계 수는 n의 제곱입니다.
• O (C ^ n) — 지수 시간 : 크기 n의 입력이 주어지면 작업을 수행하는 데 걸리는 단계의 수는 n의 제곱 (상당히 큰 수)입니다.

이 지식을 바탕으로 이러한 각 복잡성에 수반되는 단계 수를 확인하십시오.

let n = 16;

O (1) = 1 step "(awesome!)"

O (log n) = 4 steps  "(awesome!)" -- assumed base 2

O (n) = 16 steps "(pretty good!)"

O(n^2) = 256 steps "(uhh..we can work with this?)"

O(2^n) = 65,536 steps "(...)"

보시다시피 알고리즘의 복잡성에 따라 상황이 훨씬 복잡해집니다. 운 좋게도 컴퓨터는 여전히 매우 큰 복잡성을 비교적 빠르게 처리 할 수있을만큼 강력합니다.

그렇다면 Big-O 표기법으로 코드를 분석하는 방법은 무엇입니까?

다음은 이러한 지식을 야생에서 접하거나 직접 코딩 할 수있는 알고리즘에 적용하는 방법에 대한 빠르고 간단한 예입니다.

아래의 데이터 구조를 예로 들어 보겠습니다.

var friends = {
 'Mark' : true,
 'Amy' : true,
 'Carl' : false,
 'Ray' :  true,
'Laura' : false,
}
var sortedAges = [22, 24, 27, 29, 31]

키 (객체) 또는 인덱스 (배열)가 항상 한 단계 씩 걸리므로 일정한 시간이 걸리면 값을 찾습니다.

//If I know the persons name, I only have to take one step to check:

function isFriend(name){ //similar to knowing the index in an Array 
  return friends[name]; 
};

isFriend('Mark') // returns True and only took one step

function add(num1,num2){ // I have two numbers, takes one step to return the value
 return num1 + num2
}

배열의 어느 쪽에서 항목을 찾아야하는지 알면 나머지 절반을 잘라서 시간을 절약 할 수 있습니다.

//You decrease the amount of work you have to do with each step

function thisOld(num, array){
  var midPoint = Math.floor( array.length /2 );
  if( array[midPoint] === num) return true;
  if( array[midPoint] < num ) --> only look at second half of the array
  if( array[midpoint] > num ) --> only look at first half of the array
  //recursively repeat until you arrive at your solution
  
}

thisOld(29, sortedAges) // returns true 

//Notes
 //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation.
 //This solution works because our Array is sorted
 //Recursive solutions are often logarithmic
 //We'll get into recursion in another post!

작업을 수행하려면 배열 또는 목록의 모든 항목을 살펴 봐야합니다. 단일 for 루프는 거의 항상 선형 시간입니다. 또한 indexOf와 같은 배열 메소드도 선형 시간입니다. 루핑 과정에서 추상화되었습니다.

//The number of steps you take is directly correlated to the your input size

function addAges(array){
  var sum = 0;
  for (let i=0 ; i < array.length; i++){  //has to go through each value
    sum += array[i]
  }
 return sum;
}

addAges(sortedAges) //133

중첩 된 for 루프는 다른 선형 연산 (또는 n * n = n²) 내에서 선형 연산을 실행하기 때문에 2 차 시간입니다.

//The number of steps you take is your input size squared

function addedAges(array){
  var addedAge = [];
    for (let i=0 ; i < array.length; i++){ //has to go through each value
      for(let j=i+1 ; j < array.length ; j++){ //and go through them again
        addedAge.push(array[i] + array[j]);
      }
    }
  return addedAge;
}

addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ]

//Notes
 //Nested for loops. If one for loop is linear time (n)
 //Then two nested for loops are (n * n) or (n^2) Quadratic!

지수 시간은 일반적으로 그 정도를 모르고 가능한 모든 조합 또는 순열을 시도해야하는 상황을위한 것입니다.

//The number of steps it takes to accomplish a task is a constant to the n power

//Thought example
 //Trying to find every combination of letters for a password of length n

빠르게 실행되어야하는 코드를 작성할 때마다 시간 복잡도 분석을 수행해야합니다.

문제를 해결하기위한 다양한 경로가있는 경우 가장 먼저 작동하는 솔루션을 만드는 것이 현명합니다. 그러나 장기적으로는 가능한 한 빠르고 효율적으로 실행되는 솔루션이 필요합니다.

문제 해결 과정에 도움이되도록 다음과 같이 간단한 질문을합니다.

1. 이 문제가 해결되었는가? 예 =>
2. 이 작업에 시간을 갖는가? 예 => 3번으로, 아니오 => 나중에 다시 돌아와서 6 단계로 가십시오.
3. 모든 엣지 케이스에 커버했습니까? 예 =>
4. 내 복잡성이 가능한 한 낮습니까? 아니오 => 새로운 방법 또는 수정으로 재 작성하십시요 -> 1번 단계로 다시 가십시오. , 예 => 5번으로 가십시오.
5. 코드가 D.R.Y 합니까? 예 =>
6. 만족한가! 아니오 => 다시 D.R.Y로 짜고나서 만족해라.

문제를 해결하려고 할 때마다 시간 복잡성을 분석하십시오. 로그 실행에서 더 나은 개발자가 될 것입니다. 팀원과 사용자가 당신을 좋아할 것입니다.

다시 말하지만 알고리즘이든 프로그래밍 방식이든 프로그래머가 직면하게 될 대부분의 문제는 수백 가지의 방법으로 해결할 수는 없지만 수십 가지가 될 것입니다. 문제 해결 방법이 다를 수 있지만 여전히 문제를 해결합니다.

집합을 사용할지 또는 그래프를 사용하여 데이터를 저장할지 여부를 결정할 수 있습니다. 팀 프로젝트에 Angular, React 또는 Backbone을 사용할지 여부를 결정할 수 있습니다. 이러한 솔루션은 모두 동일한 문제를 다른 방식으로 해결합니다.

이를 감안할 때 이러한 문제에 대한“올바른”또는“최상의”답변이 있다고 말하기는 어렵습니다. 그러나 주어진 문제에 대해“더 나은”또는“더 나쁜”답변이 있다고 말할 수 있습니다.

이전 예제 중 하나를 사용하면 팀의 절반이 경험이있는 팀 프로젝트에 React를 사용하는 것이 더 좋으므로 시작하고 실행하는 데 시간이 덜 걸립니다.

더 나은 솔루션을 설명하는 능력은 일반적으로 시간 복잡성 분석과 유사합니다.

간단히 말해서 문제를 해결하려면 잘 해결하십시오. Big-O를 사용하여 방법을 파악하십시오.

최종 요약은 다음과 같습니다.

• O (1) — 상수 시간 : 알고리즘이 작업을 수행하는 데 단 한 단계 만 걸립니다.
• O (log n) — 로그 시간 : 작업을 수행하는 데 걸리는 단계 수는 각 단계마다 일부 요인에 의해 줄어 듭니다.
• O (n) — 선형 시간 : 필요한 단계 수는 직접 관련되어 있습니다 (1-1).
• O (n²) — 2 차 시간 : 작업을 수행하는 데 걸리는 단계 수는 n의 제곱입니다.
• O (C ^ n) — 지수 : 작업을 수행하는 데 걸리는 단계 수는 n 제곱 (상수)에 대한 상수입니다.