Яке питання - така відповідь. )
Оцінюється кількість дій. Часто це призводить до деяких рекурентним співвідношенням, які в тій чи іншій мірі важко вирішити - хоча є і готові спільні рішення, так що оцінити багато алгоритми не так вже й складно.
Однак треба враховувати, що при оцінці складності алгоритму потрібно розглядати використовувані структури даних - наприклад, в алгоритмі Дейкстри багато що залежить від того, як реалізована чергу з пріоритетами, та й взагалі в алгоритмах на графах багато що залежить від уявлення графа - списками суміжності або матрицею.
В якості найпростішого прикладу - звичайне множення матриць nxn - кожен елемент нової матриці виходить шляхом перемноження і підсумовування творів елементів відповідного рядка і стовпця. Довжина рядка / стовпця - n. разом, O (n) операцій для обчислення одного елементу результуючої матриці. Всього їх n 2 - разом, складність алгоритму O (n 3).
відповідь дан 19 лют в 7:29
Також як з іншими "навскидку" оцінками (заснованими на інтуїції), суть в уже засвоєному досвіді: в доступності будівельних блоків, якими ви можете оперувати несвідомо в обраній галузі, завдяки цілеспрямованій практиці.
Можна навіть не знати як щось конкретно реалізовано. Наприклад, якщо алгоритм на якомусь етапі вимагає сортування випадкових даних, то розумно припустити O (n log n) для алгоритму, заснованого на порівняннях, незалежно від конкретної реалізації. Або при пошуку в таблиці в базі даних, якщо рядків багато (коли про big O має сенс говорити), можна очікувати що добротна реалізація індекс створить (пошук з O (n) в O (log n) перетворюється). У разі сумнівів, можна виміряти.
Для пошуку й перевірити інтуїтивний відповідь, можна рекурентні вирази або часткові суми побудувати, які за допомогою комп'ютера обчислити. Так як є O (c * n) == O (n) і O (n * n + n) == O (n * n) і інші спрощують перетворення, то багато алгоритми можна звести до невеликого числа базових випадків. Процес вимагає уважності, але досить прямолінійний (особливо якщо задіяти що-небудь на зразок wolframalpha, Maple, Maxima, sympy). How to find time complexity of an algorithm.
Відповідно є випадки, коли концентровані зусилля, використовуючи очевидні підходи, результат не дають, тоді варто відволіктися на якийсь час, переключитися на інші завдання. Осяяння може прийти в найнесподіваніший момент (але це вже за рамками "навскидку").
Подивіться які алгоритми використовуються в задачах, які вам цікаві. Нові алгоритми з кращого складністю не кожен день з'являються.
Почніть з самого простого коду на вашій мові, framework і дізнайтеся його складність (наприклад, "видалення за індексом елемента з масиву"). Знаючи складність для елементарних конструкцій, знайдіть складність для блоків коду (складених з цих конструкцій), з якими ви часто зустрічаєтеся.
Можна в зворотну сторону: почати з більш високорівневого коду і поступово спускатися нижче за рівнями абстракції, поки до відомих блоків не дійдете (додавання фіксованих чисел, які в машинному слові відвідуються: O (1). Якщо довільне число n взяти, то O (log n) - пропорційно кількості біт в числі). Див. Таблицю складнощів за часом.
Практика, поки більшість повсякденного цікавого вам коду не зможете навскидку оцінити.