Algorithm efficiency
An algorithm describes the method to solve a computational problem. Programmers and computer scientists should use or write efficient algorithms. Algorithm efficiency is typically measured by the algorithm's computational complexity. Computational complexity is the amount of resources used by the algorithm. The most common resources considered are the runtime and memory usage.
Runtime complexity, best case, and worst case
An algorithm's runtime complexity is a function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N. Runtime complexity is discussed in more detail elsewhere.
Because an algorithm's runtime may vary significantly based on the input data, a common approach is to identify best and worst case scenarios. An algorithm's best case is the scenario where the algorithm does the minimum possible number of operations. An algorithm's worst case is the scenario where the algorithm does the maximum possible number of operations.
Input data size must remain a variable
A best case or worst case scenario describes contents of the algorithm's input data only. The input data size must remain a variable, N. Otherwise, the overwhelming majority of algorithms would have a best case of N=0, since no input data would be processed. In both theory and practice, saying "the best case is when the algorithm doesn't process any data" is not useful. Complexity analysis always treats the input data size as a variable.
✔ 1. N이 0이 되면 안되므로 항상 변수로 생각한다고 했으므로 답이 될 수 없음.
✔ 2. 만약 숫자 3을 만났을 때 반환하고 못 만났다면 그냥 3을 반환하는 경우를 생각해 보자.
만약 list안에 숫자 3이 아예 없다면 best와 worst가 모두 똑같겠지
Space complexity
An algorithm's space complexity is a function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N. Ex: The space complexity of an algorithm that duplicates a list of numbers is S(N) = 2N + k, where k is a constant representing memory used for things like the loop counter and list pointers.
Space complexity includes the input data and additional memory allocated by the algorithm. An algorithm's auxiliary space complexity is the space complexity not including the input data. Ex: An algorithm to find the maximum number in a list will have a space complexity of S(N) = N + k, but an auxiliary space complexity of S(N) = k, where k is a constant.
✔ 3. 최악의 경우 evensList의 사이즈가 N이 되고, constant k까지 해서 space가 N+k
✔ 4. 최선의 경우 evensList의 사이즈가 0이 되고, constant k까지 해서 space가 0+k
