java - 用于查找数组中最大数字的递归算法的运行时间复杂度是多少。将其与迭代循环代码进行比较

Question

我已经在迭代循环代码中编写了最大数的代码。我发现代码的运行时间复杂度是 O(n)。最大数量的递归代码的运行时间复杂度是多少，它与迭代循环有何不同。哪个会更好。我的迭代循环代码是

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); 
} 

Answer 1

正确的递归代码(假设数组至少有 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) 的额外空间开销。

为什么递归代码的时间复杂度为 O(n) ？

它解决了 n-1 个较小的问题。并且根据第 n-1 个问题的结果，在 O(1) 时间内解决了第 n 个问题。

递归代码如何工作？

如果您有一个具有 n 大小的数组，则该数组的最大元素是
1. 最后一个元素array[n-1]，或
2. n-1 大小的数组的最大元素。

要计算 n-1 大小的数组的结果，请重复类似的操作。

基本情况是，当数组中只有一个元素时，这就是最大值。