Space complexity
Space Complexity is a concept in theoretical computer science, specifically Complexity Theory, which is used to measure and describe the efficiency of an algori…
Space Complexity is a concept in theoretical computer science, specifically Complexity Theory, which is used to measure and describe the efficiency of an algorithm in terms of the amount of memory they will require to store the information they need. Algorithms, when implemented in computer programs, require two main resources when the program is executed: time and memory. Memory, particularly, may be expensive in large quantities. Therefore it is often desirable to make modifications to an algorithm so as to reduce its space complexity, that is, make it use less memory when run.
Space Complexity and Input Size
As with time complexity, space complexity is usually given in terms of the input size, using Big-O notation. Usually, the input size is given as a number that refers to an amount of elements that need to be considered to solve a problem. The space complexity is then often given as a function that gets larger as increases. This function indicates how quickly the memory requirement grows when is very large.
Auxiliary Space Complexity refers to the amount of storage space that the algorithm will use besides the storage space which is already used for the input data. As the input data for any algorithm will have to be stored in memory, it is often more important to know whether the algorithm can operate "in place", i.e. without a need for memory that will grow as gets large.
Relationship With Time Complexity
The other resource that algorithms consume is time. The so-called time complexity of an algorithm is measured in the same way and is more commonly taught first in courses covering algorithms. It is worth noting that there is a relationship between the auxiliary space complexity of an algorithm and its time complexity: since the former measures the amount of data that is created after the algorithm begins, the time complexity is always greater than the auxiliary space complexity.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.