сложности (бесконечные алгоритмы) Calculate алгоритма

Учитывая этот кусок кода Java:сложности (бесконечные алгоритмы) Calculate алгоритма

import java.util.Scanner; 

class BreakWhileLoop { 
    public static void main(String[] args) { 
    int n; 

    Scanner input = new Scanner(System.in); 

    while (true) { 
     System.out.println("Input an integer"); 
     n = input.nextInt(); 

     if (n == 0) { 
     break; 
     } 
     System.out.println("You entered " + n); 
    } 
    } 
}

Давайте возьмем этот частный случай: the user will always enter any integer except 0.

1. Может ли я рассматривать этот код как алгоритм?

2.Если да, как рассчитать его сложность?

Благодаря

источник

2014-11-02 MCHAppy

Хорошо .. задайте следующие вопросы: 1) Что делает этот алгоритм? 2) На каких данных работает этот алгоритм? – Rotem

Имеет ли смысл говорить о своей сложности, когда она даже не заканчивается? Ничего не нужно масштабировать. – harold

Чтобы рассчитать сложность времени, вам нужно знать входные данные. Поэтому, если вы знаете, какая числовая последовательность, заканчивающаяся нулем, пользователь загружает в этот «алгоритм», то он является линейным. Но, честно говоря, нет смысла называть этот алгоритм ... –

Чтобы избежать тривиальных ответов, давайте ослабить постановку проблемы, удалив условие except 0.

Тогда да, это алгоритм, мы можем назвать его 0 acceptor.

Предполагая, что пользовательский ввод принимает постоянное время, временная сложность O(N), где N - это длина ненулевой последовательности.

источник

2014-11-02 10:36:43

Очевидно, что если 'N' неограничен, то и сложность. –

«Алгоритм является конечной последовательностью четко определенных инструкций для вычисления функции (или исполняющей процедуру), которая заканчивается в хорошо определенном заканчивающемся состоянии.»

Как взяты из: https://softwareengineering.stackexchange.com/questions/69083/what-is-an-algorithm

Если пользователь всегда будет держать ввода значений, то это не алгоритм.

источник

2014-11-02 10:30:52

Он будет работать вечно. Сложность времени используется для указания верхней границы времени, в течение которого алгоритмы выполняются в зависимости от ввода. Поскольку ваш код будет работать вечно независимо от того, что представляет собой вход, бессмысленно говорить о его временной сложности.

источник

2014-11-02 10:31:00

Но давайте рассмотрим, что у нас есть длинный алгоритм, включающий вышеприведенный фрагмент кода, не логично ли говорить о временной сложности? – MCHAppy

Как я сказал, сложность времени используется для указания верхнего предела времени на основе ввода пользователя. Бессмысленно говорить о временной сложности кода, который гарантированно работает навсегда. –

Взаимодействие - более мощная парадигма, чем алгоритмы на основе правил для решения вычислительных задач, опрокидывая преобладающее представление о том, что все вычисления выражаются в виде алгоритмов.

Вы можете следить за подробностями и доказательствами этого в this renowned article by Wegner, что означает «Почему взаимодействие более мощное, чем алгоритм?»

источник

2017-01-23 13:38:01 OmG

сложности (бесконечные алгоритмы) Calculate алгоритма

ответ

Смежные вопросы