|
LP0 ON FIRE posted:theoretically there's nothing that proves that there could be something faster depending on which you're using for the appropriate case, or was it proven in any use case? ??? https://en.m.wikipedia.org/wiki/Big_Omega_function ??? O is an upper bound, asymptotic less than or equals. Omega is a lower bound, asymptotic greater than or equals. There are many ways to go about proving something. Induction is often a good strategy. OldAlias fucked around with this message at 05:43 on Jun 8, 2017 |
#
¿
Jun 7, 2017 21:12
|
|
|
|
| # ¿ May 14, 2024 08:26 |
|
|
ex n log n is the best, worst and expected case of mergesort. so it's often preferred for its consistency and in general sorting can be said to be n log n right. but quicksort or radix sort or a number of others can be faster depending on how your data is structured, or what it is you're ordering. quicksort has a best case of n but can have a worst case of n^2 if the data is mostly ordered or if the pivot is consistently the largest or smallest element. I hope I'm not stating some obvious poo poo, I don't know what your background is
|
|
#
¿
Jun 7, 2017 21:32
|
|
|
LP0 ON FIRE posted:thanks that is good info no. that is accounted for in the algorithm. take a linear walk through sorted data for example, comparing each element to see if the element is greater than the one before. that's at most n operations where n is the size of the input. if you want to know if an algorithm is formally correct beforehand you should read into induction and proofs and symbolic butt's post e; beaten by cis autodrag OldAlias fucked around with this message at 22:14 on Jun 7, 2017 |
|
#
¿
Jun 7, 2017 21:59
|
|
|
flakeloaf posted:i'm doing one right now and the book is incomprehensible cs texts are lol and a racket. unless the material and tests closely follow it find a bunch of other resources as supplement. our course used sedgewick which is worthless for a good portion of the class. he invents his own notation which no one uses because he has problems with Big O - but his problems are addressed with theta and omega, which i guess he never heard of. visualizations are good (animations, graphs (assuming proper scales) etc) for an intuitive understanding of things. the math you just have to keep hammering at until you recognize patterns and strategies and then everything is almost mechanical OldAlias fucked around with this message at 19:09 on Jun 9, 2017 |
|
#
¿
Jun 9, 2017 18:50
|
|
|
f ~ g. it's basically theta, but if f ~ g then f / g -> 1 (in theta the implied constant is arbitrary)
|
|
#
¿
Jun 9, 2017 20:28
|
|
|
|
| # ¿ May 14, 2024 08:26 |
|
|
if you don't have at least a basic understanding of asymptotic analysis then you're a terrible programmer
|
|
#
¿
Jun 11, 2017 19:02
|
|