数据结构1-时空复杂度

爱被打了一巴掌 2022-05-27 02:35 216阅读 0赞

#                                            数据结构1-时空复杂度 #

程序设计=算法+数据结构。   
算法：解决特点问题的求解步骤的描述，表现为计算机中的有限条指令。   
算法具有确定性、可行性、有穷性三个特性。

### 时间复杂度 ###

简言之，时间复杂度就估算程序需要执行的次数。   
一般求解时间复杂度的计算方法：   
1、用常数1取代运行时间中的所有加法常数   
2、在修改后的运行函数中，只保留最高项。   
3、如果最高阶项系数存在且不是1，则去掉这个系数。

栗子1.1
    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<Windows.h>
    int main()
    {
        int arr[] = { 9, 5, 6, 4, 7, 8, 2, 13, 5, 20 };
        int sz = sizeof(arr) / sizeof(arr[0]);
        int i = 0, j = 0;
        int flag = 0;
        for (i = 0; i < sz - 1; i++)
        {
            for (j = 0; j < sz - i - 1; j++)
            {
                if (arr[j - 1]>arr[j])
                {
                    arr[j - 1] ^= arr[j];
                    arr[j] ^= arr[j - 1];
                    arr[j - 1] ^= arr[j];
                    flag = 1;
                }   
            }
            if (flag == 0)
                break;
        }
        for (int k = 0; k < sz; k++)
            printf("%d ", arr[k]);
        printf("\n");
        system("pause");
        return 0;
    }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31

上述经典的冒泡排序，其时间复杂度是O(n^2)。

### 空间复杂度 ###

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间。   
我们知道了栗子1.1的空间复杂度是O(1)。

### 二分查找法的递归与非递归 ###

非递归二分查找
    #include<stdio.h>
    #include<Windows.h>
    #include<assert.h>
    int binary_search(int*arr, int len, int key)
    {
        assert(arr);
        int left = 0;
        int right = len - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + ((right-left) >> 1);
            if (arr[mid] > key)
            {
                right = mid - 1;
            }
            else if (arr[mid] < key)
            {
                left = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
    void Test()
    {
        int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int len = sizeof(arr) / sizeof(arr[0]);
    
        printf("%d\n", binary_search(arr, len, 0));
        printf("%d\n", binary_search(arr, len, 1));
        printf("%d\n", binary_search(arr, len, 2));
        printf("%d\n", binary_search(arr, len, 3));
        printf("%d\n", binary_search(arr, len, 4));
        printf("%d\n", binary_search(arr, len, 5));
        printf("%d\n", binary_search(arr, len, 6));
        printf("%d\n", binary_search(arr, len, 7));
        printf("%d\n", binary_search(arr, len, 8));
        printf("%d\n", binary_search(arr, len, 9));
        printf("%d\n", binary_search(arr, len, 10));
    }
    int main()
    {
        Test();
        system("pause");
        return 0;
    }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51

递归法
    #include<stdio.h>
    #include<Windows.h>
    #include<assert.h>
    int binary_search(int*arr, int left, int right,int key)
    {
        assert(arr != NULL);
        while (left<=right)
        {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > key)
                return binary_search(arr, left, mid - 1, key);
            else if (arr[mid] < key)
                return binary_search(arr, mid + 1, right, key);
            else
                return mid;
        }
        return -1;
    }
    void test()
    {
        int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int len = sizeof(arr) / sizeof(arr[0]);
    
    
        printf("%d\n", binary_search(arr, 0, 9, 0));
        printf("%d\n", binary_search(arr, 0, 9, 1));
        printf("%d\n", binary_search(arr, 0, 9, 2));
        printf("%d\n", binary_search(arr, 0, 9, 3));
        printf("%d\n", binary_search(arr, 0, 9, 4));
        printf("%d\n", binary_search(arr, 0, 9, 5));
        printf("%d\n", binary_search(arr, 0, 9, 6));
        printf("%d\n", binary_search(arr, 0, 9, 7));
        printf("%d\n", binary_search(arr, 0, 9, 8));
        printf("%d\n", binary_search(arr, 0, 9, 9));
        printf("%d\n", binary_search(arr, 0, 9, 10));
    }
    int main()
    {
        //Test();
        test();
        system("pause");
        return 0;
    }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44

![70][]

### 斐波那契递归与非递归 ###

//通过斐波那契的三种实现方法，体验空闲复杂度的重要性
    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<Windows.h>
    //非递归
    //long long fib(int n)
    //{ 
    // int f0 = 0, f1 = 1, f2 = n;
    // if (n < 3)
    // return 1;
    // else
    // { 
    // for (int i = 2; i <= n; ++i)
    // { 
    // f2 = f1 + f0;
    // f0 = f1;
    // f1 = f2;
    // }
    // }
    // return f2;
    //}
    
    ![这里我们可以看到非递归法计算第350个斐波那契数页几乎不需要时间，尽管第350个fib数已经溢出。](https://img-blog.csdn.net/20180322185922710?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2tlcnNfeGlhb3dlaQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)
    
    
    //递归
    long long fib(int n)
    {
        if (n < 3)
            return 1;
        else
        {
            return fib(n - 1) + fib(n - 2);
        }
    }
    
    
    ![递归法计算第35个斐波那契数：](https://img-blog.csdn.net/2018032218555759?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2tlcnNfeGlhb3dlaQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)
    int main()
    {
        int n = 0;
        scanf("%d", &n);
        fib(n);
        printf("%d\n", fib(n));
        system("pause");
        return 0;
    }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47

### 尾递归 ###

在斐波那契数的计算中，我们可以知道递归法计算fib数时，它的空间复杂度是O(n)，需要花费的时间很多。上述递归法在计算fib数时候，做了很多冗余的工作，比如f(4)=f(3)+f(2)，而f(3)=f(2)+f(1)。f(2)就被计算了两次，类似的，当计算的fib数稍大时候，冗余就非常大了。实际上，递归法我们可以优化：

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<Windows.h>
    long long fib(int n, int c1, int c2)
    {
        if (n < 3)
            return c1;
        else
        {
            printf("%d ", c1 + c2);
            return fib(n - 1, c2, c1 + c2);
        }
    }
    
    
    int main()
    {
        int n = 0;
        scanf("%d", &n);
        long start_time = GetTickCount();
        fib(n,1,1);
        long end_time = GetTickCount();
        printf("斐波那契函数实现时间：%ld\n", end_time - start_time);
        system("pause");
        return 0;
    }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26

![70 1][]

[70]: /images/20220527/e212cff8b8754677b96340fc22339ee2.png
[70 1]: /images/20220527/e37b6852a56c414f938d660eaea8892e.png