Измерь это. Выполните операции с линейно увеличивающимися операндами и начертите время на диаграмме.
Не забудьте прогреть JVM (несколько прогонов), чтобы получить действительные результаты тестов.
Если операции линейные O (n), квадратичные O (n ^ 2), полиномиальные или экспоненциальные должны быть очевидными.
РЕДАКТИРОВАТЬ: Хотя вы можете дать алгоритмы теоретические границы, они не могут быть такими полезными на практике. Прежде всего, сложность не дает фактора. Некоторые линейные или субквадратичные алгоритмы просто бесполезны, потому что они потребляют так много времени и ресурсов, что их недостаточно для решения задачи (например, умножение матрицы Копперсмит-Винограда).
Тогда ваши вычисления могут иметь все клуджи, которые вы можете обнаружить только экспериментально. Есть готовые алгоритмы, которые ничего не делают для решения проблемы, но для ускорения реального решателя (матричная обработка). Существуют неоптимальные реализации. При увеличении длины ваша скорость может резко упасть (отсутствует кеш, перемещение памяти и т. Д.). Поэтому для практических целей советую заняться экспериментами.
Лучше всего удваивать каждый раз длину ввода и сравнивать времена.
И да, вы действительно узнаете, имеет ли алгоритм n ^ 1,5 или n ^ 1,8 сложности. Просто четверной
длина ввода и вам нужно только половину времени для 1,5 вместо 2. Вы снова получаете почти половину времени для 1,8, если умножить длину на 256 раз.