Изучите О() нотацию. Приведите реалистичный пример, в котором получается, что О(N*N) быстрее, чем О(N) для некоторых N>10.
Ну что ж господа попробуем разобрать что это. Я сразу и не понял, все конечно зависит от алгоритмов которые выполняются они могут до определенного n выполнятся с большей скоростью чем для O(n), просто нужно смотреть, да и вообще мне сказали, что n как правило к бесконечности в реальной жизни редко стремится и бывает используют те алгоритмы которые отвечают условию O(n*n), а те что O(n) их не используют потому что они только быстро работают когда n к бесконечности стремится, а если не стремится, а обычно на компьютерах память ограничена, то O(n*n) работает быстрее.
От в общем тот примерчик что мне на форуме подкинули:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// допустим N = 100 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // some code } } // имеем 10000 итераций, в big-O нотации это O(n * n) // при той же N = 100 for (int i = 0; i < N * 1000000; i++) { // some code } // имеем 100000000 итераций, в big-O нотации это O(n) |
Из примера видно что все зависит от алгоритма, первый алгоритм будет работать быстрее для некоторых N, пока N не начнет стремится к бесконечности и число 1000000 им можно будет пренебречь.
[youtube]http://www.youtube.com/watch?v=1dLGybh_4aU[/youtube]
[youtube]http://www.youtube.com/watch?v=CgYxQ9jlna8[/youtube]