算法复杂度


计算资源

时间复杂度:

程序运行需要的时间。

空间复杂度:

程序运行需要的存储空间。

说明

1、定义全局数组无限制,且自动初始化为0或NULL;
2、main函数栈空间为8MB, 可定义整形数组大小 <= 2000000位,1整形 = 4字节 = 32位二进制;
3、笔记本电脑的计算能力大约每秒千万次数量级;而oj系统每秒能运行1亿次;


时间计算
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;

int main() {
    int k = 0, n = 1e8;
    clock_t start, end;
    start = clock(); // 开始
    
    for (int i = 0; i < n; i++) ++k;
    
    end = clock(); // 结束
    
    cout << "t = " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    
    return 0;
}

/*
时间复杂度分析:
循环n次,运行效率为线性时间,即 O(n);
在CPU为i5-8250U、内存为8GB、64位操作系统下:
n = 1e8时, t = 0.164s;
n = 19e时, t = 1.645s;
*/

下用一道例题为例

hdu1425 “sort”

链接: http://acm.hdu.edu.cn/showproblem.php?pid=1425

思路:对100万个数排序,再输出前 m 大的数。

//法一冒泡排序

#include <bits/stdc++.h>

using namespace std;

int a[1000001];
#define swap(a, b) {a ^= b; b ^= a; a ^= b;}
int n, m;
void bubble_sort() {
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (*(a + j) > *(a + j + 1))
                swap(*(a + j), *(a + j + 1));
        }
    }
}
int main() {
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 1; i <= n; i++) scanf("%d", a + i); // 数据太多只能用 scanf 输入;
        bubble_sort();
        for (int i = n; i >= n - m + 1; i--) {
            if (!(i ^ (n - m + 1))) printf("%d\n", *(a + i));
            else printf("%d ", *(a + i));
        }
        memset(a, 0, sizeof(a));
    }
    return 0;
}
/*
分析:

时间复杂度

bubble_sort()函数有两重循环,循环次数为 n-1 + n-2 + n-3 + ... + 1 = n^2 / 2; 而在swap(a, b)执行了3次操作;总计算次数为 3n^2 / 2;复杂度记为 O(n*n); 故 n < 10000 冒泡排序才勉强过;

空间复杂度

程序使用 int a[1000001]存储数据,且 bubble_sort() 没有使用额外空间,故约使用 4MB 空间;
// 法二 快速排序

#include <bits/stdc++.h>

using namespace std;

int a[1000001];
#define swap(a, b) {a ^= b; b ^= a; a ^= b;}
int n, m;

int main() {
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        sort(a + 1, a + n + 1);
        for (int i = n; i >= n - m + 1; i--) {
            if (!(i ^ (n - m + 1))) printf("%d\n", *(a + i));
            else printf("%d ", *(a + i));
        }
        memset(a, 0, sizeof(a));
    }
    return 0;
} 

基于STL的 sort() 函数,是改良版的快速排序;
时间复杂度为O(nlgn); 正好通过,提交运行时间为600ms;
//法三哈希排序

#include <bits/stdc++.h>

using namespace std;
#define MAXN 1000001
int a[MAXN];
int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 0; i < n; i++) {
            int t;
            scanf("%d", &t);
            a[500000 + t] = 1; // 数字t登记在 t + 500000的位置
        }
        for (int i = MAXN - 1; m > 0; i--) {
            if (*(a + i)) {
                if (m > 1) printf("%d ", i - 500000);
                else printf("%d\n", i - 500000);
                --m;
            }
        }
        memset(a, 0, sizeof(a));
    }
    
    return 0;
}
思路:

在输入数字t的时候,在a[500000 + t] 这个位置记录a[500000 + t] = 1 记录 t ,在输出的时候逐个检查 a[i] , if (a[i] == 1) 表示这个数存在, 打印出前 m 个数;

哈希排序以空间换时间,时间复杂度为O(n), 比快排快;

在 hdu 提交运行时间 500ms ;

算法的选择


对于一个问题必有多种解法, 低效算法编码时间往往低于高效算法编码时间。


算法的定义与评估

1、定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。


算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,称为时间复杂度。其中f(n)是问题规模n的某个函数。


2、推导大O阶方法
    推导大O阶:
    1、用常数1取代运行时间中的所有加法常数
    2、在修改后的运行次数函数中,只保留最高阶项
    3、如果最高阶项存在且不是i,则去除与这个项相乘的常数得到的结果就是大O阶


  3、常见的时间复杂度

执行次数函数 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n^2+2n+1 O(n^2) 平方阶
5log2n+19 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) nlogn阶
6n3+2n2+3n+4 O(n^3) 立方阶
2^n O(2^n)

常用时间复杂度所耗费的时间从小到大依次是:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < (n!) < O(n^n);
N^3以后都不应该出现在算法中。


4、最坏情况和平均情况:
最坏情况运行时间是一种保证,那就是运行时间不会再坏了,在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况运行时间



文章作者: Axieyun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
评论
评论
  目录