Чернова:Времева сложност
 | Това е чернова на статия от Инкубатора на българската Уикипедия.
ВАЖНО: Това не е енциклопедична статия. Инкубаторът се използва за създаване на статии от нови и неопитни потребители, както и в други случаи, когато статия не отговаря на критериите на Уикипедия. Възможно е информацията в тази страница да е невярна, тенденциозна или дори напълно неподходяща за Уикипедия. Информация за авторите на черновата
Причините за това най-вероятно са, че тя не отговаря на някои от изискванията на Уикипедия.
Прегледайте статиите в Портал:Избрани статии. В началото се фокусирайте върху качеството, а не върху количеството. Вижте следващите въпроси за повече подробности. Запомнете, че не всяка друга статия в Уикипедия непременно е качествена и подходяща като пример за следване. Понякога дори съвсем некачествени статии може да не са били забелязани от останалите редактори, затова не използвайте аргументи като „Защо тази статия може да я има, а моята – която е като нея – не може?“. Ако забележите некачествени статии, поправете ги или ги предложете за изтриване на У:СИ.
Още:
Полезно е също да имате предвид следните ръководства: Този списък също не е изчерпателен. Допълнителна информация конкретно за Инкубатора може да намерите в неговия регламент.
Полезна информация как да започнете статия има в следните страници:
Този шаблон се поставя автоматично от бот на всички статии в Инкубатора. Моля, не го премахвайте! |
В теоретичната компютърна наука времевата сложност е изчислителната сложност, която описва количеството компютърно време, необходимо за изпълнение на алгоритъм. Времевата сложност обикновено се оценява чрез преброяване на броя на елементарните операции, извършени от алгоритъма, като се предполага, че всяка елементарна операция отнема фиксирано време за изпълнение. По този начин се приема, че количеството отнето време и броят на елементарните операции, извършени от алгоритъма, са свързани с постоянен фактор .
Константно време
редактиранеАлгоритъмът се изпълнява за константно време (също написано време ), ако стойността на (сложността на алгоритъма) е ограничена от стойност, независеща от размера на входа. Например, достъпът до всеки отделен елемент в масив отнема постоянно време, тъй като е нужна само една операция, за да се намери. Сходно на това, намиране на минималната стойност в масив, сортиран във възходящ ред: това е първият елемент. Намирането на минималната стойност в несортиран масив обаче не е операция с постоянно време, тъй като е необходимо сканиране на всеки елемент в масива, за да се определи минималната стойност. Следователно това е линейна времева операция, отнемаща време. Ако обаче броят на елементите е известен предварително и не се променя, все още може да се каже, че такъв алгоритъм работи в постоянно време.
Въпреки името "константно време", времето за изпълнение не трябва да не зависи от размера на проблема, но горната граница за времето за изпълнение трябва да бъде независима от размера на проблема. Например задачата „сменете стойностите на a и b, ако е необходимо, така че " се нарича константно време, въпреки че времето може да зависи от това дали условието е вече вярно или не. Въпреки това, има някаква константа t, за която необходимото време винаги е най-много t .
Логаритмично време
редактиранеЛинейно време
редактиранеАлгоритъм се казва, че отнема линейно време(или време), ако времевата му сложност е . Неформално това означава, че времето за изпълнение нараства най-много линейно с размера на входа. По-точно, това означава, че има константа , така че времето за изпълнение е най-много за всеки вход с размер n. Например, процедура, която събира всички елементи на списък, ще изисква време, пропорционално на дължината на списъка, ако време за събиране е константно или ограничено от константа.
Линейното време е най-добрата възможна времева сложност в ситуации, в които алгоритъмът трябва последователно да прочете целия си вход. Поради това са инвестирани много изследвания в откриването на алгоритми, показващи линейно време или поне почти линейно време. Това изследване включва софтуерни и хардуерни методи. Има няколко хардуерни технологии, които използват паралелизма, за да осигурят това. Пример е адресируема към съдържание памет . Концепцията за линейно време се използва в алгоритми за сравняване на низове като алгоритъма за търсене на низове на Бойър–Мур и алгоритъма на Уконен .