Както импровизирано оцени сложността на времето преливане комин на алгоритъм на Руски

Какво въпрос - отговор. )

Очакван брой действия. Това често води до някои повтарящи се отношения, които до известна степен е трудно да се реши - въпреки че има готови цялостни решения, така че много алгоритми за оценка не е толкова трудно.
Въпреки това, ние трябва да имаме предвид, че при оценката на сложността на алгоритъма трябва да се счита, използвани структури от данни - например, Алгоритъм на Дейкстра, много зависи от начина, по който изпълняват приоритетна опашка, а всъщност в графика алгоритми, много зависи от представителството графика - списъците или близост матрица.

Като прост пример - обичайните матрица умножение NxN - всеки елемент на новата матрица, произведена чрез умножаване и сумиране на продуктите от елементи на съответния ред и колона. Дължината низ / колона - п. общо, О (п) операции за изчисляване на един елемент на матрицата на резултат. Общо 2 п - общо сложност на алгоритъм O (п 3).

Отговорено 19 февруари в 07:29

Както и от други "безцеремонни" прогнози (на базата на интуицията), които вече са в процеса на обучение са: в наличието на градивни елементи, които можете да работят несъзнателно в избраната сфера, благодарение на целенасочена практика.

Дори не можеш да знаеш нещо конкретно изпълнение. Например, ако на алгоритъма в някакъв етап изисква сортиране случайни данни, логично е да се предположи, O (п влезте н) за алгоритъм на базата на сравнения, независимо от конкретната реализация. Или когато погледнете в таблицата в базата данни, ако линиите много (когато един голям О е смислено да се каже), можем да очакваме, че индексът ще създаде изпълнение с добро качество (търсене на O (N) за O (влезте н) се превръща). В случай на съмнение, може да се измери.

За да намерите или проверете интуитивен отговор, че е възможно повтарящи се изрази или частични суми да се изгради, че с помощта на компютър, за да се изчисли. Тъй като има O (C * п) == О (п) и вода (п * п + п) == О (п * п), а другият да се опрости превръщане, много алгоритми могат да бъдат намалени до малък брой базови случаи. Процесът изисква грижи, но сравнително лесно (особено ако се използва нещо като WolframAlpha, Maple, Maxima, sympy). Как да намерите време сложност на алгоритъм.

Съответно, има случаи, когато концентрирано усилие, като се използва подход, очевидно, резултатът не е дадено, то е необходимо да избягат за малко, да преминете към други задачи. Вдъхновение може да дойде в най-неочакван момент (но това е извън обхвата на "без да се замисля").

Виж какво алгоритми се използват в приложения, които ви интересуват. Нови алгоритми с по-добра сложност не се появяват всеки ден.

Започнете с прост код на вашия език, рамка и да видим неговата сложност (например, "премахване на индекса на елемента на масива на"). Знаейки, сложността на елементарни структури, намерете трудността за кодови блокове (съставен от тези структури), с когото често се запознаем.

Възможно е в обратната посока: да се започне с код на високо равнище, и постепенно се спускат по-ниски нива на абстракция като на известните блоковете, които достигат (добавяне на фиксирани номера, които са машина дума посети :. O (1) В случай на произволен брой н вземе O (Дневник п) - пропорционално на броя на битовете са включени). Cm. Таблица по време на усложнения.

Практика, докато по-голямата част от ежедневието интересен код няма да бъде в състояние да направи оценка на случаен принцип.