Back to Basics: Algorithmic Complexity - Amir Kirsh & Adam Segoli Schubert - CppCon 2021 |
Description: https://cppcon.org/ https://github.com/CppCon/CppCon2020 --- When you're designing a program, how do you choose appropriate data structures and algorithms? How do you know when the proposed design is likely to be "too slow," without benchmarking the finished code? How can you avoid introducing inefficiencies into the code as you write it, without burning yourself out on "premature optimization"? Why do people always say the inner loop is the most important? How is it that the 10x speedup you committed yesterday was completely wiped out by a mere 2x increase in site traffic today? In this session, we'll explore the notion of algorithmic complexity, especially as it relates to the data structures and algorithms provided by the C++ standard library, such as std::sort, std::find, and std::binary_search. With just a bit of informal math, we'll define "big-O notation" and demonstrate the differences between complexity classes such as O(1), O(lg n), and O(n). We'll show how to determine the big-O complexity of your own functions by counting loops (including the loops hidden inside STL algorithms and overloaded operators). Then we'll show how we can use limits — or a bit of geometric intuition — to determine that certain algorithms run in linear time despite their complex inner structure, and explain what we mean when we say that vector::push_back runs in "amortized constant time." Finally, we'll discuss ways to trade off space against time, or setup time against query time, and discuss some practical considerations such as constant factors and physical implementation limits. --- Amir Kirsh Amir Kirsh is both a Lecturer and a practitioner. Teaching at the Academic College of Tel-Aviv-Yaffo and at Tel-Aviv University while keeping hands on, mainly on C++, as a Dev Advocate at Incredibuild and previously as the Chief Programmer at Comverse. Amir is also one of the organizers of the CoreCpp conference in Tel-Aviv and the CoreCpp meetup group and a member of the Israeli ISO C++ National Body. Adam Segoli Schubert Adam is a software consultant, programming instructor, and part of the Dev Advocate office at Incredibuild. He also collaborates on projects which focus on decentralization, parallelization, and blockchain, with the objective of advancing transparency, freely available distributed knowledge, and autonomy. --- Videos Filmed & Edited by Bash Films: http://www.BashFilms.com YouTube Channel Managed by Digital Medium Ltd https://events.digital-medium.co.uk Register Now For CppCon 2022: https://cppcon.org/registration/ 
|
