Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
→ 인풋 : 정수로 주어진 배열 nums
→ 아웃풋 : answer배열. answer[i]는 nums[i]를 제외한 nums의 다른 요소들의 곱셈의 결과임.
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
→ 곱셈 결과 범위 -2,147,483,648부터 2,147,483,647까지
You must write an algorithm that runs in O(n) time and without using the division operation.
→ 나눗셈 사용하지 않도록.
→ O(n) 시간 복잡도 갖도록.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
→ O(1) 공간 복잡도 가능?
아무래도 하나의 데이터(변수)만 활용해서 계산해야한다면 for 문이 중첩되거나 계산이 복잡해질 것.
알고리즘에서 사용할 수 있는 공간(메모리)이 넉넉하면, 더 빨리 결과를 도출할 수 있을 것 같다. (트레이드 오프)
다른 아티클에서도 보이더라 https://techsauce.medium.com/how-to-reduce-time-complexity-from-quadratic-to-linear-in-array-based-coding-interview-problems-b4f86ffcc7eb
다른 풀이에서도 배열 순회를 2단계로 나누어 이전 단계의 연산 결과를 기억했다가 재활용하는 접근이 유효했다.
입력값(인풋) 증가에 따라 run time 혹은 공간이 얼마나 증가하는가에 대한 것. O(n) 은 일반적으로 선형 시간 복잡도로도 표현할 수 있는데, 알고리즘의 실행 시간이 입력 크기에 따라 선형적으로 증가한다는 것을 의미.
https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/
In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem. Big O notation is also used in many other fields to provide similar estimates.
Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions. Basically, it tells you how fast a function grows or declines. Landau's symbol comes from the name of the German number theoretician Edmund Landau who invented the notation. The letter O is used because the rate of growth of a function is also called its order.