Computational complexity | Wikipedia audio article

This is an audio version of the Wikipedia Article: https://en.wikipedia.org/wiki/Computational_complexity 00:01:33 1 Resources 00:01:42 1.1 Time 00:02:27 1.2 Space 00:02:42 1.3 Others 00:04:17 2 Complexity as a function of input size 00:05:30 3 Asymptotic complexity 00:07:54 4 Models of computation 00:08:22 4.1 Deterministic models 00:09:16 4.2 Non-deterministic computation 00:10:24 4.3 Parallel and distributed computation 00:11:57 4.4 Quantum computing 00:13:05 5 Problem complexity (lower bounds) 00:14:02 6 Use in algorithm design 00:18:22 7 See also 00:20:24 8 References Listening is a more natural way of learning, when compared to reading. Written language only began at around 3200 BC, but spoken language has existed long ago. Learning by listening is a great way to: - increases imagination and understanding - improves your listening skills - improves your own spoken accent - learn while on the move - reduce eye strain Now learn the vast amount of general knowledge available on Wikipedia through audio (audio article). You could even learn subconsciously by playing the audio while you are sleeping! If you are planning to listen a lot, you could try using a bone conduction headphone, or a standard speaker instead of an earphone. Listen on Google Assistant through Extra Audio: https://assistant.google.com/services/invoke/uid/0000001a130b3f91 Other Wikipedia audio articles at: https://www.youtube.com/results?search_query=wikipedia+tts Upload your own Wikipedia articles through: https://github.com/nodef/wikipedia-tts Speaking Rate: 0.9568617800371617 Voice name: en-US-Wavenet-F "I cannot teach anybody anything, I can only make them think." - Socrates SUMMARY ======= In computer science, the computational complexity, or simply complexity of an algorithm is the amount of resources required for running it. The computational complexity of a problem is the minimum of the complexities of all possible algorithms for this problem (including the unknown algorithms). As the amount of needed resources varies with the input, the complexity is generally expressed as a function n → f(n), where n is the size of the input, and f(n) is either the worst-case complexity, that is the maximum of the amount of resources that are needed for all inputs of size n, or the average-case complexity, that is average of the amount of resources over all input of size n. When the nature of the resources is not explicitly given, this is usually the time needed for running the algorithm, and one talks of time complexity. However, this depends on the computer that is used, and the time is generally expressed as the number of needed elementary operations, which are supposed to take a constant time on a given computer, and to change by a constant factor when one changes of computer. Otherwise, the resource that is considered is often the size of the memory that is needed, and one talks of space complexity. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Clearly, both areas are strongly related, as the complexity of an algorithm is always an upper bound of the complexity of the problem solved by this algorithm.