Ned Batchelder - Big-O: How Code Slows as Data Grows - PyCon 2018
Speaker: Ned Batchelder
Big-O is a computer science technique for analyzing how code performs as data gets larger. It's a very handy tool for the working programmer, but it's often shrouded in off-putting mathematics.
In this talk, I'll teach you what you need to know about Big-O, and how to use it to keep your programs running well. Big-O helps you choose the data structures and algorithms that will let your code work efficiently even on large data sets.
You can understand Big-O even if you aren't a theoretical computer science math nerd. Big-O isn't as mystical as it appears. It's wrapped in mathematical trappings, but doesn't have to be more than a common-sense assessment of how your code will behave.
Slides can be found at: speakerdeck.com/pycon2018 and github.com/PyCon/2018-slides
Пікірлер: 30
Great presentation. May seem a little basic at first to someone somewhat familiar with the topic, but everyone should appreciate how well he distills the concepts in such a short amount of time
Straight to the point. All in a nutshell. Thank you so much for clarity, briefness and of course precision and ease of grasping these concepts. Low Japanese bow of honor for you, my friend Ned
Great talk this made the concept a lot easier to understand, thanks !
one of the best presentations. thank you for such a nice talk.
I love this presentation.
Great presentation
Really awesome presentation 👍 🐍
Really great talk Ned.
I don't normally comment on KZread videos but this is an excellent video. And I'm already familiar with big O too, he just says it so much better.
Great talk
Great!
Great presentation. Big-O is an important topic and difficult to comprehend. I also read the Toxic experts' blog post. It is very well written. That is so true. Unfortunately, these toxic experts idealogy says, "either learn everything the way I know or do not even think about it." As long as they are commenting on your posts, "anonymously," we can say it is OK, and we can ignore them. However, sometimes they are in charge of your grades, or they are your manuscripts' reviewers. That is the sad part of the story.
13:16 does this mean we don’t care about accuracy? Why would we only look through half of the list? Thanks in advance.
A better way is to say how the speed of a process changes as the input size changes. Who said it only has to grow? For example, if your task was to quickly sort 1,048,576 numbers such as 3.1416, someone might say using an O(n^2) algorithm wont work in a reasonable amount of time, but that is not really true. For example, if you bust up those numbers into 1,024 groups of 1,024 numbers each, bubble sort each group, and then merge them together, you can get it to run in a reasonable amount of time. D&C (Divide and Conquer) is a wonderful thing. Not sure what the new big O would be but the runtime will for sure be MUCH better. Orders of magnitude better.
Thank you! Could you please explain to me why 26:41 there is O(N) in the second example? Because we do multiplication and powering 2 to 61?
@Grayhamper
Жыл бұрын
Python calculates a Hash for every element in the set. If by chance, the hashes for two elements are the same in the eyes of the hash algorithm, it takes longer to calculate them, because these "hash collisions" need to be resolved. And that takes O(N).
Why at 28:50 all the numbers i*(2**61-1) have the same hash. These numbers are different so should their hashes. I am a bit confused.
@1234567qwerification
6 жыл бұрын
The word 'hash' (see "Hash_function" in Wikipedia) means that some numbers have the same hash. E.g., if you sum all digits of your birth date, you'll get a number. If I do the same with my birth date and get the same number, it will not mean that we were born the same day (it would be possible, but not for sure (an example of "hash collision") ).
Nice talk. The part about small numbers though got me confused. If N is how much data you have, can you have less than 1. I think the N, the data or the iterations can be only non zero integers.
@brnddi
5 жыл бұрын
The graph there is a little confusing because the lines on it don't actually represent any real algorithms. An algorithm that does absolutely nothing is O(1), but runs in zero time. An algorithm that has one thousand consecutive copypasted lines of 'i++' is O(1), but does 1000 operations. On the other hand, an algorithm that takes a parameter "N" and then does 'i++' N times would be O(n), but only does N operations; this would make it run faster than the O(1) algorithm if your N is, say, 100 (as it would only perform 100 operations).
Why is it O(N) when all the hashes are exactly the same ? @26:40
I couldn't find the slides if u could please drop the link to it
if "..n is usually small" why the hell almost every company ask about it on the interview in addition asking to invert a binary tree, neglecting more important software engineering principles? :)
pg was here (breadcrumbs)
Where are the slides?
@user-ex8vj4qe7n
5 жыл бұрын
You can look up in the description :)
Wow what brilliant insight 🙄