Мы часто считаем асимптотики различных алгоритмов и, исходя из этого, пытаемся понять, будет ли решение достаточно быстрым. Но в некоторых случаях такая оценка будет далека от истины.

1. Вставка и удаление в vector (и операции с памятью вроде memcpy и memmove)

Пусть у нас есть изначально пустой vector v и мы 10^5 раз вызовем v.insert(v.begin(), rand()). По cppreference.com каждая такая вставка требует O(n) времени, т.е. получаем 10^10 операций, не с точностью до константы. Но замерим время на практике: ideone. На ideone это занимает 650 мс, на Codeforces 1500 мс, но в любом случае, это не похоже на обычные 10^10 операций. Также, часто в задачах на строки участники что-то делают с ними за квадрат, и это тоже иногда заходит (при n = 1e5 или даже 3e5).

2. Деление чисел с плавающей точкой

Интуитивно кажется, что деление int на int должно быть быстрее double на double, а тем более long double на long double. И на некотрых серверах (ideone, например) это действительно так. Но не на всех. Возьмём для теста два кода: целые числа и с плавающей запятой. Запуск на C++14 даёт 220 мс для первого и 130 мс для второго. Более того, long double на Codeforces тоже отработал за 130 мс, хотя long double содержит в себе не только все значения int, но и long long.

3. sqrt(double) и sqrt(long double)

Опять же, логично предположить, что sqrt(double) должен быть быстрее, т.к. double и пямяти занимает меньше, и точность меньше. На Codeforces они работают примерно одинаково. Но на ideone sqrt(long double) оказался быстрее.

4. pow

Мне казалось, что pow работает за O(1). Но, как оказалось pow(x, 1) и pow(x, 2) заметно быстрее pow(x, произвольный double) и даже pow(x, другие целые). Ну и чуть более понятный факт: pow(x, 0.5) заметно дольше sqrt(x).

5. floor(x) и int(x)

Для double int работает в 2 и более раз быстрее floor. Для long double наоборот.

Пишите в комментариях интересные факты, известные вам и не названные здесь, желательно тоже с кодом-бенчмарком.