Kselax.ru

Hacker Kselax — the best hacker in the world

Menu
  • Блог
  • Контакты
  • wp plugin генератор
  • Русский
    • Русский
    • English
Menu

Нотация O большого пример.

Posted on 1 июля, 20138 июля, 2013 by admin

Изучите О() нотацию. Приведите реалистичный пример, в котором получается, что О(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]

Добавить комментарий Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Рубрики

  • C++ (293)
  • JavaScript (1)
  • linux (1)
  • MFC (39)
  • node.js (2)
  • React (3)
  • uncategorized (2)
  • vBulletin (5)
  • Visual Studio (9)
  • wordpress (18)
  • Разное (35)

Метки

Ajax bootstrap CentOS CLI expressjs FormData GDlib google Invisible reCAPTCHA JWT media MFC php react-router-dom redux repository wordpress RTTI STL vBulletin vector Visual Studio WINAPI wordpress wp-plugins XMLHttpRequest Двоичное дерево Задачи С++ Игры С++ Исключения С++ О-большое Операторы_С++ Перегрузка операторов С++ Поиск С++ Потоки Проектирование_С++ С++ Типы_С++ Типы С++ Шаблоны С++ библиотеки локализация макросы С++ сортировка С++

Свежие комментарии

  • RA3PKJ к записи visual C++, создание диалоговых окон.
  • JasonReant к записи Создание и использование статических библиотек .lib в visual studio.
  • MyWin2020 к записи Программка для заполнения форума на vBulletin 3.8.7
  • ScottJip к записи Создание и использование статических библиотек .lib в visual studio.
  • ArnoldKig к записи Создание и использование статических библиотек .lib в visual studio.
©2021 Kselax.ru Theme by ThemeGiant