Замена итерације формулом
Један од важних савета за побољшање сложености алгоритама је тај да не терамо рачунар да врши дуготрајна израчунавања која се могу извршити и “пешке”, применом математике. Наиме, често се одређене вредности израчунавају применом итеративних поступака. На пример, збир елемената неког низа израчунавамо додавањем једног по једног елемента. То даје тражени резултат, али и одузима неко време. Постоје ситуације када су елементи који се обрађују правилни и када се коначан резултат може добити применом неке задате формуле, без примене итеративног поступка. На пример, ако знамо да треба сабрати првих \(n\) елемената низа \(1, 2, 3, \ldots, n\), нема потребе да примењујемо итеративни поступак сабирања чија је сложеност \(O(n)\), већ је довољно да у времену \(O(1)\) применимо Гаусову формулу на основу које знамо да је
\[1 + 2 + \ldots + n = \frac{n(n+1)}{2}\]
Још неке формуле се често могу употребити за смањење сложености (али и за саму анализу сложености), па ћемо их у наставку навести.
Аритметички и геометријски низ
Сличне формуле које су нам корисне су формуле за \(n\)-ти члан и збир првих \(n\) елемената аритметичког низа \(a_0\), \(a_1 = a_0 + d\), \(a_2 = a_0 + 2d\), \(\ldots\).
\[a_i = a_0 + id, \qquad \sum_{i=0}^{n} a_i = \frac{(n+1)(a_0 + a_n)}{2},\]
као и за \(n\)-ти члан и збир првих \(n\) елемената геометријског низа \(a_0\), \(a_1 = a_0\cdot q\), \(a_2 = a_0 \cdot q^2\), \(\ldots\)
\[a_i = a_0\cdot q^i, \qquad \sum_{i=0}^{n} a_i = a_0\frac{1-q^{n+1}}{1-q}.\]
Збирови степена
\[1^2 + 2^2 + \ldots + n^2 = \sum_{k=1}^n k^2 = \frac{n\cdot (n + \frac{1}{2}) \cdot (n+1)}{3}\]
\[1^3+2^3+\ldots + n^3 = \sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2.\]
Комбинаторика
- Број начина да се из скупа од \(n\) различитих бројева извуку два броја \(a < b\) је \(\binom{n}{2} = \frac{n(n-1)}{2}\).
- Број начина да се из скупа од \(n\) различитих бројева извуку три броја \(a < b < c\) је \(\binom{n}{3} = \frac{n(n-1)(n-2)}{3\cdot 2}\).