课程: Java Algorithms

How to describe the time complexity of an algorithm - Java教程

课程: Java Algorithms

开始一个月试用 购买团队方案

How to describe the time complexity of an algorithm

“

- [Instructor] Some algorithms are more efficient than others. And we often describe an algorithm's efficiency using Big-O notation. Big-O notation allows us to compare algorithms independent of input size. Let's say we wanted to compare search algorithms for a list. If the item we're searching for will always be the first or last element of a list, we can say it takes constant time or O(1) time. No matter what the input sizes, we just have to check the first and last element to find our answer. If the item we're searching for is somewhere in the list but we don't know where, we might have to check every single element. In the best case, the item we're looking for would be the first element we check. In the worst case, the item would not exist in the list and we would have to check every single element. Most algorithms have the best case and worst case performance time. And they're often not the same. For this search algorithm, the best case would be constant time. The first item we check is the item we're searching for. The worst case would be linear time. As the input size increases, the search time increases. With Big-O notation, the worst case would be O(n) where n is the input size. In deciding which algorithm to use, we often use the worst case time complexity as a deciding factor. However, if the worst case happens only 5% of the time, then it might be useful to consider the average case or the best case as well. The more informed assumptions we're able to make about our data, the more efficient we can make our algorithms. With the first search algorithm, we assume that the item we're searching for will be the first or last element. This cuts the best and worst case down to just constant time. With the other algorithm, we do not make this assumption. This lengthens the algorithm's worst time to O(n). Some other common time complexities an algorithm can have are logarithmic or O(log(n)), an exponential, O of N squared. Constant time is the most efficient out of these, with n factorial being the least efficient. With n as a generic input size, we're able to compare these notations in terms of efficiency. We also use this notation to describe space complexity. Does the algorithm use constant space or as much space as the size of the input? This can be another factor in deciding which algorithm to use to complete a task. No matter how efficient your algorithms are, Big-O notation allows you to compare them regardless of input size.

内容