知识点6（计算的复杂度(computational|知识点6：计算的复杂度(computational complexity)）
If we have a really efficient algorithm, we can minimize the amount of resources we have available to deal with it.
If we have an algorithm that is going to take a lot of work to process a really large set of data, it's going to require more and more resources, which is money, RAM, all that kind of stuff.
When we talk about the complexity of an algorithm -- which sometimes you'll hear it referred to as time complexity or space complexity but we're just going to call complexity -- we're generally talking about the worst-case scenario.
We generally call the worst-case runtime of an algorithm big-O.
Sometimes, though, we do care about the best-case scenario. If the data is everything we wanted it to be and it was absolutely perfect and we were sending this perfect set of data through our algorithm.
How would it handle in that situation?
We sometimes refer to that as big-Omega, so in contrast with big-O, we have big-Omega.
Big-Omega for the best-case scenario.
Big-O for the worst-case scenario.
Generally, when we talk about the complexity of an algorithm, we're talking about the worst-case scenario.
Well, what is a data set?
It means whatever makes the most sense in context, to be honest（在程序里有用的那些都是数据集）. If we have an algorithm, the Processes Strings -- we're probably talking about the size of the string. That's the data set -- the size, the number of characters that make up the string.
If we're talking about an algorithm that processes files, we might be talking about how many kilobytes comprise that file. And that's the data set.
If we're talking about an algorithm that handles arrays more generally, such as sorting algorithms or searching algorithms, we're probably talking about the number of elements that comprise an array.
Now, we can measure an algorithm-- in particular, when I say we can measure an algorithm, I mean we can measure how many resources（内存或时间） it takes up. Whether those resources are, how many bytes of RAM-- or megabytes of RAM it uses. Or how much time it takes to run.
we can call this measure, arbitrarily, f of n. Where n is the number of elements in the data set. And f of n is how many units of resources does it require to process that data.
Now, we actually don't care about what f of n is exactly. We're just going to talk about what f of n is approximately or what it tends to.
And the tendency of an algorithm is dictated by its highest order term.
And we can see what I mean by that by takinga look at a more concrete example:
文章图片
So let's say that we have three different algorithms.
Now again, we really aren't going to get into this level of detail. I'm really just have these up here as an illustration of a point that I'm going to be making in a second, which is that we only really care about the tendency of things as the data sets get bigger.
So if the data set is small, there's actually a pretty big difference in these algorithms. The third algorithm there takes 13 times longer, 13 times the amount of resources to run relative to the first one.
If our data set is size 10, which is bigger, but not necessarily huge, we can see that there's actually a bit of a difference. The third algorithm becomes more efficient. It's about actually 40%-- or 60% more efficient. It takes 40% the amount of time. It can run-- it can take 400 units of resources to process a data set of size 10.
Whereas the first algorithm, by contrast, takes 1,000 units of resources to process a data set of size 10. But look what happens as our numbers get even bigger.
Now, the difference between these algorithms start to become a little less apparent(指第三行：n=1000). And the fact that there are lower-order terms -- or rather, terms with lower exponents -- start to become irrelevant.
If a data set is of size 1,000 and the first algorithm runs in a billion steps. And the second algorithm runs in a billion and a million steps. And the third algorithm runs in just shy of a billion steps. It's pretty much a billion steps.
Those lower-order terms start to become really irrelevant.
And just to really hammer home the point -- if the data input is of size a million -- all three of these pretty much take one quintillion -- if my math is correct -- steps to process a data input of size a million. That's a lot of steps.
And the fact that one of them might take a couple 100,000, or a couple 100 million even less when we're talking about a number that big-- it's kind of irrelevant.
They all tend to take approximately n cubed, and so we would actually refer to all of these algorithms as being on the order of n cubed or big-O of n cubed.
文章图片
Here's a list of some of the more common computational complexity classes that we'll encounter in algorithms, generally.
These are ordered from generally fastest at the top, to generally slowest at the bottom.
So constant time algorithms tend to be the fastest, regardless of the size of the data input you pass in. They always take one operation or one unit of resources to deal with. It might be 2, it might be 3, it might be 4. But it's a constant number. It doesn't vary.
Logarithmic time algorithms are slightly better. And a really good example of a logarithmic time algorithm you've surely seen by now is the tearing apart of the phone book to find Mike Smith in the phone book.
We cut the problem in half. And so as n gets larger and larger and larger -- in fact, every time you double n, it only takes one more step.
So that's a lot better than, say, linear time. Which is if you double n, it takes double the number of steps. If you triple n, it takes triple the number of steps. One step per unit.
Then things get a little more-- little less great from there. You have linear rhythmic time, sometimes called log linear time or just n log n. And we'll an example of an algorithm that runs in n log n, which is still better than quadratic time-- n squared. Or polynomial time, n two any number greater than two. Or exponential time, which is even worse-- C to the n.
So some constant number raised to the power of the size of the input. So if there's 1,000-- if the data input is of size 1,000, it would take C to the 1,000th power. It's a lot worse than polynomial time.
Factorial time is even worse. And in fact, there really do exist infinite time algorithms, such as, so-called stupid sort-- whose job is to randomly shuffle an array and then check to see whether it's sorted.
And if it's not, randomly shuffle the array again and check to see whether it's sorted. And as you can probably imagine-- you can imagine a situation where in the worst-case, that will never actually start with the array. That algorithm would run forever. And so that would be an infinite time algorithm.
some examples:
文章图片
文章图片
【知识点6（计算的复杂度(computational|知识点6：计算的复杂度(computational complexity)）】一个for循环是O(n)，而for内嵌一个for循环是n乘以n，即O(n*2)。
推荐阅读
- 不负光阴的100天——第三十四天
- Go 每日一库之 bitset
- 迈向高级的Java面试突围课|完结
- javascript|精读《useRef 与 createRef 的区别》
- java|从2.7.0-2.7.5版本，Dubbo调用链路是如何提升30%性能的
- 杀手的挽歌
- html5|基于 HTML5 Canvas 的 3D 热力云图效果
- python|LeetCode 删除链表的倒数第 N 个节点
- 【Android|【Android volley】Android库Volley的使用介绍
- spring|springcloud之ribbon的使用