java空间复杂度如何分析?时间复杂度呢?

TheDisguiser 2020-09-15 15:03:41 java常见问答 8579

在各种算法中都会有它的时间及空间复杂度,将它们分析出来以达到最优可以极大的提升算法速度,下面就来看看它们有哪些分析方法。

一、实现二分查找算法的递归及时间复杂度空间复杂度分析

代码:

#
define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<string.h>
#include<assert.h>
int BinarySearch(int arr[], int len, int num)
{
    assert(arr);
    int left = 0;
    int right = len - 1;
    int mid;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (num > arr[mid])
        {
            left = mid + 1;
        }
        else if (num < arr[mid])
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
int main()
{
    int arr[] = {
        1
        , 2
        , 3
        , 4
        , 5
        , 6
        , 7
        , 8
        , 9
    };
    int length = sizeof(arr) / sizeof(arr[0]);
    int aim = 9;
    int result;
    result = BinarySearch(arr, length, aim);
    if (result == -1)
    {
        printf("Can't find %d\n", aim);
    }
    else
    {
        printf("%d at %d postion\n", aim, result + 1);
    }
    return 0;
}

二分查找时,会每次都在原有查找内容进行二分,因此时间复杂度为O(log2 n)

又因为变量值创建一次,所以空间复杂度为O(1)

二、实现斐波那契数列的递归及时间复杂度空间复杂度分析

代码:

int FeiBoNaCciInteration(int a, int b, int num)
{
    int c;
    if (num <= 0)
        return -1;
    else if (num == 1)
        return a;
    else if (num == 2)
        return b;
    else
    {
        while (num - 2)
        {
            c = a + b;
            a = b;
            b = c;
            num--;
        }
        return c;
    }
}
int main()
{
    int n;
    int result;
    printf("Input n\n");
    scanf("%d", & n);
    result = FeiBoNaCciInteration(2, 3, n); //可自定义输入第一个数和第二个数
    if (result == -1)
    {
        printf("Input Error!\n");
    }
    else
    {
        printf("n is %d\n", result);
    }
    return 0;
}

时间复杂度O(n)

空间复杂度为O(1)

以上就是本篇文章的所有内容,有想了解更多java常见问题及解决方法的小伙伴,可以关注我们网站了解详情。

推荐阅读:

java空间免备案是什么?有哪些免费免备案空间?

java空间换时间该如何实现?

java空间租用需要注意些什么?