Thursday, January 14th 2016
- Binary Search Tree
- Storing numerical values (important! numerical values can be compared, which is the crux of the mechanic of this data structure!) in relation to one another in a, hopefully, balanced tree. While the time complexity for this isn't constant, it's not linear either. It's logarithmic. An increase in the number of inputs only slightly increases the time for processing. We shift through values fairly quickly, simply by sorting and nesting them within a series of true/false values. Particularly, is this value larger or small than the value your looking for?
- [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
- v: 4 ||||||||
- is v = 11? false. v < 11? true-->
- value=5? false. v<5? true ->
- v=3? false. v<3? false ->
- v=4? true!
- took 4 tries. If we double'd this array, we may add 1 or 2 steps, despite the 2 * n increase in n. While n increases, our time complexity only increases at a marginal rate. 4 - > 5 or 4 -> 6.
http://bigocheatsheet.com/
http://algs4.cs.princeton.edu/32bst/
No comments:
Post a Comment