Определение времени работы алгоритма

@RomanFlash · Регистрация: 02.06.2016

Author24 — интернет-сервис помощи студентам

Помогите надо определить время работы алгоримта

C

Boolean: Function (integer: array[])
 
for i=0 to <наибольший индекс массива> - 1
    for j=i+1 to <наибольший индекс массива>
        if (array[i] == array[j]) then return true
    next j
next i
 
return false
 
end function

У меня получилась ерунда: О( (N^2 - N) / 2)

по этой формуле можно определить сколько шагов понадобиться совершить программе , использую этот алгоритм, чтобы проверить массив из N элементов. А как определить в какой зависимости будет возрастать количество щагов от количества элементов. Поправьте если, что не так написал.

@Shamil1 · 17.06.2016, 22:38

O(N²)

@RomanFlash · 17.06.2016, 23:31 **[ТС]**

Shamil1, неправильно!

@Shamil1 · 17.06.2016, 23:57

Сообщение от RomanFlash

Shamil1, неправильно

Как Вы пришли к такому выводу? Можете доказать?

@RomanFlash · 18.06.2016, 12:45 **[ТС]**

Shamil1, очень просто: в книге по которой я изучаю алгоритмы есть пример:

C++

Boolean: Function (integer: array[])
 
for i=0 to <наибольший индекс>
    for j=0 to <наибольший индекс>
        if (i != j) then
            if (array[i] == array[j]) then return true
            End if
    next j
next i
 
return false
 
End Funtion

Автор книги пишет, что этот алгоритм имеет время работы O(N^2), алгоритм который я указал в теме несколько отличается от этого => время работы у них не мб одинаковым.

@Shamil1 · 18.06.2016, 12:57

Сообщение от RomanFlash

алгоритм который я указал в теме несколько отличается от этого => время работы у них не мб одинаковым

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

Новые блоги и статьи
Какой локальный веб-сервер выбрать InfoMaster 19.01.2025 В современной веб-разработке локальные веб-серверы играют ключевую роль, предоставляя разработчикам надежную среду для создания, тестирования и отладки веб-приложений без необходимости использования. . .	Почему планшеты и iPad уже не так популярны, как раньше InfoMaster 19.01.2025 Эра революционных инноваций История планшетных компьютеров началась задолго до того, как эти устройства стали привычными спутниками нашей повседневной жизни. В начале 1990-х годов появились первые. . .	Как самому прошить BIOS ноутбука InfoMaster 19.01.2025 BIOS (Basic Input/ Output System) представляет собой важнейший компонент любого компьютера или ноутбука, который обеспечивает базовое взаимодействие между аппаратным и программным обеспечением. . .	Какой Linux выбрать для домашнего компьютера InfoMaster 19.01.2025 Современные реалии выбора операционной системы В современном мире выбор операционной системы для домашнего компьютера становится все более важным решением, которое может существенно повлиять на. . .	Как объединить два словаря одним выражением в Python InfoMaster 19.01.2025 В мире программирования на Python работа со словарями является неотъемлемой частью разработки. Словари представляют собой мощный инструмент для хранения и обработки данных в формате "ключ-значение". . . .	Как без исключения проверить существование файла в Python InfoMaster 19.01.2025 При разработке программного обеспечения на Python часто возникает необходимость проверить существование файла перед выполнением операций с ним. Это критически важная задача, которая помогает избежать. . .
Как определить, содержит ли строка подстроку в JavaScript InfoMaster 19.01.2025 При разработке веб-приложений часто возникает необходимость выполнять различные операции со строками, среди которых особое место занимает поиск подстрок. JavaScript предоставляет несколько встроенных. . .	Что такое метаклассы в Python InfoMaster 19.01.2025 Метаклассы в Python представляют собой один из самых мощных и одновременно сложных механизмов языка, позволяющий программистам контролировать процесс создания классов. По своей сути, метакласс. . .	Как удалить свойство из объекта JavaScript InfoMaster 19.01.2025 В современной веб-разработке объекты JavaScript играют фундаментальную роль в организации и структурировании данных. Они представляют собой контейнеры, которые хранят связанные данные и. . .	Какая разница между String и string в C# InfoMaster 19.01.2025 В языке программирования C# существует интересная особенность: для работы со строками можно использовать как String, так и string. Эта двойственность часто вызывает вопросы у разработчиков, особенно. . .	Как в Git откатить репозиторий к предыдущему коммиту InfoMaster 19.01.2025 В современной разработке программного обеспечения система контроля версий Git стала неотъемлемой частью рабочего процесса, предоставляя разработчикам мощные инструменты для управления изменениями в. . .	Как работают замыкания (closure) в JavaScript InfoMaster 19.01.2025 В мире современной веб-разработки замыкания (closures) представляют собой один из фундаментальных концептов языка JavaScript, который часто вызывает затруднения у начинающих разработчиков, но при. . .

@Shamil1 Модератор 3079 / 2228 / 462 Регистрация: 26.03.2015 Сообщений: 8,648
	17.06.2016, 22:38	2
	O(N²) 0

@RomanFlash 0 / 0 / 1 Регистрация: 02.06.2016 Сообщений: 48
	17.06.2016, 23:31 [ТС]	3
	Shamil1, неправильно! 0

@Shamil1 Модератор 3079 / 2228 / 462 Регистрация: 26.03.2015 Сообщений: 8,648
	17.06.2016, 23:57	4
	Сообщение от RomanFlash Shamil1, неправильно Как Вы пришли к такому выводу? Можете доказать? 0

@Shamil1 Модератор 3079 / 2228 / 462 Регистрация: 26.03.2015 Сообщений: 8,648
	18.06.2016, 12:57	6
	Сообщение от RomanFlash алгоритм который я указал в теме несколько отличается от этого => время работы у них не мб одинаковым Это ошибочный вывод. У разных алгоритмов может быть одинаковое "время работы" (сложность). Это связано с тем, что у разных последовательностей может быть одинаковый предел. 1

Опции темы