LeetCode - Time complexity 시간 복잡도

https://www.reddit.com/r/leetcode/comments/w26u7o/could_someone_please_explain_the_difference_in/ https://www.reddit.com/r/MLQuestions/comments/wz7s5h/can_someone_explain_time_complexity_and_what_doe/

r/MLQuestions on Reddit: Can someone explain time complexity and what doe sit has to do with data structures like LinkedList and

Could someone please explain the difference in run time? : r/leetcode

Time Complexity

- 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다. (wiki)

 

Time complexity is how long it will take a piece of code to solve a problem. This is almost always based on how much data we give the code to solve (known as n). If I ask someone how much money is in his wallet it might be a time complexity of (1) if he remembers how much he's put in there. It's time (n) if he forgot and has to count all of the bills in his wallet (and he has n of them). It's time ( n2 ) if his kids like sneaking photo copies of bills into his wallet so each one he looks at he decides to look at all the others to make sure they aren't duplicates of the one he's holding.

Time complexity in computing is looking at the code and figuring out how long it's going to take to run for an arbitrarily sized data set. We're often interested in average run time, and worst case run time.

 

* 지갑에 돈이 얼마인지 계산한다면 O(1), 얼마있는지 잊어버렸다면 다시 지갑을 n번(확인할때마다) 수행 O(n),  만약 지갑에 위조 지폐가 들어 있어 지폐를 검수 작업이 추가된다면 O(n^2)

* 시간 복잡도는 임의 데이터셋에 대한 접근시 수행 작업의 계산 횟수를 나타낸다.

 

Reply 

- 일반적으로 잘 알려진 알고리즘은 정답이라고 할 수있는 시간 복잡도를 가지고 있다.(현 기준) 따라서 너무 최적화에 집중하지 않아도 된다는 의견이 다수

- reddit, 컴퓨팅에 사용되는 알고리즘과 데이터 구조는 리소스를 파악하기 좋은 지표이다. 이 문제는 CS(Computer Science)에서 주로 다룬다. ML part에서는 기술적으로 알필요는 없다는 의견

- 데이터 구조를 잘 이해하면 더 나은 전처리 파이프라인을 구축 가능

- Gradient Descent가 잘알려진 neural network에서 사용되는 최적화 알고리즘 표본

- Non use loop O(1) , using loop O(n) using loop in loop O(n^2)