Определение алгоритмической сложности функции

@yura91 · Регистрация: 23.10.2013

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

Как можно определить алгоритмическую сложность какой нибудь функции? Ну подсчитать количество присваиваний и других операций и определить сколько времени они займут.

Добавлено через 2 часа 34 минуты
Есть для этого какие нибудь toolsы?

@KEKCoGEN · 06.11.2016, 16:49

yura91, алгоритмическая сложность не определяет сколько времени что займет. Так же она не применяется к ф-циям, а к алгоритмам. Кол-во присваиваний не влияет на сложность алгоритма.
Как расчитывать сложность можно легко нагуглить

@yura91 · 06.11.2016, 21:32 **[ТС]**

А как вообще определить сколько времени будет выполнятся определенная функция? Ну скажем я написал какую то функцию и хочу определить время ее выполнения при вызове, как это лучше сделать? И количество присваиваний влияет на время выполнения функции?? Можете пояснить.

@Serg4356 · 06.11.2016, 21:37

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

А как вообще определить сколько времени будет выполнятся определенная функция

Вводите переменную в начале программы, присваиваете ей текущее время, и вторую переменную в конце - и ей текущее время. Вторая минус первая - время выполнения вашей программы.

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

И количество присваиваний влияет на время вполнения функции?

смотря что, как и куда присваивать. Если у вас 2 массива дуриллионой длины, и вы каждому каждое присваиваете, непонятно зачем - конечно это повлияет на время выполнения.

@KEKCoGEN · 06.11.2016, 21:38

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

А как вообще определить сколько времени будет выполнятся определенная функция?

Заранее никак. Быстрота выполнения зависит от мощности системы.

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

Ну скажем я написал какую то функцию и хочу определить время ее выполнения

можно засечь время вначале и в конце, но там множество ньюансов поэтому скорее всего вы получите неверные результаты или неверно их поймете.

@yura91 · 06.11.2016, 22:47 **[ТС]**

можно засечь время вначале и в конце, но там множество ньюансов поэтому скорее всего вы получите неверные результаты или неверно их поймете.

А какие нюансы можете объяснить если не сложно?

@Serg4356 · 06.11.2016, 23:04

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

нюансы

Какие тут нюансы?)

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {
 
    public static void main(String[] args) {
 
        double a = System.nanoTime();
 
        //тут ваш код, какой угодно, например:
        int x = 0;
        for(int i = 0; i<10000000; i++){
            x++;
        }
 
        double b = System.nanoTime();
        System.out.println("Время выполнения программы в наносекундах: " + (b-a));
    }
}

@KEKCoGEN · 07.11.2016, 00:52

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

Какие тут нюансы

Для демонстрации самого очевидного и простого, возьмите свой код, запустите его 100 раз в цикле и выполните замер только последней итерации

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {
     
    public static void main(String[] args) {
 
        double res = 0;
        for(int k=0;k<100; k++) {
            double a = System.nanoTime();
     
            //тут ваш код, какой угодно, например:
            int x = 0;
            for(int i = 0; i<10000000; i++){
                x++;
            }
     
            double b = System.nanoTime();
            res = b-a;
        }
        
        System.out.println("Время выполнения программы в наносекундах: " + res);
    }
}

Думаю результат вас удивит.

Добавлено через 2 минуты

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

А какие нюансы можете объяснить если не сложно?

было бы несложно, объяснил, но микробенчмаркинг это сложная тема и уж точно не для новичков. Достаточно посмотреть на пример выше.

@Serg4356 · 07.11.2016, 19:51

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

Думаю результат вас удивит.

удивил. больше не вякаю

тем более есть чем занять вечер - гуглить микробенчмаркинг

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@yura91 3 / 27 / 2 Регистрация: 23.10.2013 Сообщений: 2,331

	Определение алгоритмической сложности функции 06.11.2016, 16:36. Показов 1112. Ответов 8 Метки нет (Все метки) Как можно определить алгоритмическую сложность какой нибудь функции? Ну подсчитать количество присваиваний и других операций и определить сколько времени они займут. Добавлено через 2 часа 34 минуты Есть для этого какие нибудь toolsы? 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	06.11.2016, 16:49
	yura91, алгоритмическая сложность не определяет сколько времени что займет. Так же она не применяется к ф-циям, а к алгоритмам. Кол-во присваиваний не влияет на сложность алгоритма. Как расчитывать сложность можно легко нагуглить 0

@yura91 3 / 27 / 2 Регистрация: 23.10.2013 Сообщений: 2,331
	06.11.2016, 21:32 [ТС]
	А как вообще определить сколько времени будет выполнятся определенная функция? Ну скажем я написал какую то функцию и хочу определить время ее выполнения при вызове, как это лучше сделать? И количество присваиваний влияет на время выполнения функции?? Можете пояснить. 0