Какова будет сложность во время выполнения для рекурсивного алгоритма поиска наибольшего числа в массиве. Сравните это с итеративным кодом l oop - PullRequest
Новая
       59

Какова будет сложность во время выполнения для рекурсивного алгоритма поиска наибольшего числа в массиве. Сравните это с итеративным кодом l oop

0 голосов
/ 03 апреля 2020

Я написал код для наибольшего числа в коде итерации l oop. И я обнаружил, что сложность времени выполнения для кода O (n). Какова будет сложность времени выполнения для рекурсивного кода наибольшего числа и чем он будет отличаться от итерации l oop. Который будет лучше. Мой код для итерации l oop: 

package com.bharat;

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the numbers you want to add in the array: ");
        int number = scanner.nextInt();
        int[] myIntgersArray = getIntegers(number);

        System.out.println(Arrays.toString(myIntgersArray));
        System.out.println(findBiggestNumber(myIntgersArray));
    }


    public static int[] getIntegers(int number){
        Scanner scanner = new Scanner(System.in);
        int[] values= new int[number];
        for (int i =0;i<values.length;i++){
            values[i]=scanner.nextInt();
        }
        return values;
    }

    public static int  findBiggestNumber(int[] array){
        int i=0;
        int biggestNumber = array[i];
        for ( i = 0;i<array.length;i++){
            if (array[i]>biggestNumber){
                biggestNumber=array[i];
            }
        }
        return biggestNumber;
    }
}

Рекурсивный код, который был размещен в комментариях - 

public static int findBiggestNumber(int[] array, int number) { 
    int highestNumber = array[0]; 

    if (number==1) { 
        return highestNumber; 
    } 
    else { 
        if (highestNumber < array[number]) {
            array[number] = highestNumber; 
            return highestNumber; 
        } 
    }

    return findBiggestNumber(array, number-1); 
}

1 Ответ

0 голосов
/ 03 апреля 2020

Исправить рекурсивный код (при условии, что в массиве есть хотя бы 1 элемент) - 

public static int findBiggestNumber(int[] array, int number)
{ 

    if(number == 1)             //only one element is there in array
    {
        return array[number -  1];
    }


    return Math.max( array[number - 1] , findBiggestNumber(array,number-1) ); 
}

Рекурсивный код выполняется за O (n) времени, но имеет дополнительные пробелы O (n) из-за стек рекурсивных вызовов функций.

Why the recursive code has O(n) time ?

Это решает n-1 меньшие проблемы. И n -ая задача решается в O (1) раз из результата n-1 -ой задачи.

How the recursive code works ?

Если у вас есть массив с массивом n размера , тогда максимальный элемент этого массива либо
1. последний элемент array[n-1], либо
2. максимальный элемент массива n-1.

Чтобы вычислить результат для массива размером n-1, вы повторите то же самое.

Базовый случай, когда у вас есть только один элемент в массиве, тогда это максимум.

...