Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Нотация O большое - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Нахождение минимального числа http://www.cyberforum.ru/cpp-beginners/thread919846.html
Есть такое выражение int min=((a<b&&a<c)?a:(b<c)?b:c); оно находит минимальное из 3-х чисел. Меня интересует как оно работает? Что за ? знак и двоеточие. кому несложно, словесно опишите работу...
C++ Правильное завершение потока при фатальной ошибке Создаю поток через CreateThread(....), поток выполняется и в какой то момент в нем происходит ожидаемая фатальная ошибка. На экран выводится мессенжбокс с сообщением "Fatal Error...", если я нажимаю... http://www.cyberforum.ru/cpp-beginners/thread919834.html
Сервис C++
у меня есть приложение, которое делает скрин монитора и отправляет подключенным к нему компам Но проблема стоит в следующем когда я запускаю это приложение как сервис то все скрины черные. как тут...
Как сложить ряд чисел? C++
Даны натуральное число n, действительные числа {a}_{1},...,{a}_{n}. Вычислить {a}_{1}+,...,+{a}_{n} .
C++ Классы с++ vs глобальные массивы http://www.cyberforum.ru/cpp-beginners/thread919814.html
Изучаю с++ классы и хочу уточнить такие моменты В моей проге используется куча много мерных глобальных массивов 1) Правильно понимаю что используя классы и static массивы внутри класса, я...
C++ Обход графа в ширину Подскажите, как во время обхода графа в ширину помечать вершины как четные и не четные? подробнее

Показать сообщение отдельно
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,273
Записей в блоге: 2
Завершенные тесты: 1
08.07.2013, 21:40
Цитата Сообщение от ninja2 Посмотреть сообщение
Приведите реалистичный пример, в котором получается, что О(N*N) быстрее, чем О(N) для некоторых N>10.
Неужели "Гуру С++" не может придумать, казалось бы, очевидный пример?
Хорошо, не гуру поможет:
C++
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)
итого O (N * N) быстрее, чем O(N).
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru