网站后台编辑器上传不了图片,网建短信通,淘宝引流推广平台,晨雷文化传媒网站建设目录 本节目标1. 算法效率1.1 如何衡量一个算法的好坏1.2 算法的复杂度 2.时间复杂度2.1 时间复杂度的概念2.1.1 入门习题2.1.2 进阶习题 2.2 常见时间复杂度 3. 空间复杂度3.1 常见空间复杂度 本节目标
算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度oj练习
1. 算法… 目录 本节目标1. 算法效率1.1 如何衡量一个算法的好坏1.2 算法的复杂度 2.时间复杂度2.1 时间复杂度的概念2.1.1 入门习题2.1.2 进阶习题 2.2 常见时间复杂度 3. 空间复杂度3.1 常见空间复杂度 本节目标
算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度oj练习
1. 算法效率
1.1 如何衡量一个算法的好坏
1.2 算法的复杂度
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2.时间复杂度
2.1 时间复杂度的概念
时间复杂度的定义在计算机科学中**算法的时间复杂度是一个函数**它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
2.1.1 入门习题 示例1斐波那契数列 // 请计算一下Func1中count语句总共执行了多少次
void Func1(int N)
{int count 0;for (int i 0; i N; i){for (int j 0; j N; j){count;}}for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}分析时间复杂度为 O(N) 示例2 // 计算Func2的时间复杂度
void Func2(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
} 示例2分析:时间复杂度为 O(N) 示例3 // 计算Func3的时间复杂度
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N; k){count;}printf(%d\n, count);
}示例3分析 时间复杂度为 O(MN) 示例4 void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}示例4分析 时间复杂度为 O(1) 2.1.2 进阶习题 示例1 // 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0)break;}
}示例1分析时间复杂度为 O(N^2 示例2 // 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}示例2分析时间复杂度为 O(logN) logN在算法分析中表示是底数为2对数为N。有些地方会写成lgN 示例3 // 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
} 示例3分析时间复杂度为O(N) 示例4 // 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}示例4分析时间复杂度为O(2^N) 2.2 常见时间复杂度
一般算法常见的复杂度如下 3. 空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
3.1 常见空间复杂度
大部分空间复杂度不是O(1)就是ON 示例1 void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0)break;}
}示例1分析:空间复杂度是O1 实例2 long long* Fibonacci(size_t n)
{if (n 0)return NULL;long long* fibArray (long long*)malloc((n 1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n; i){fibArray[i] fibArray[i - 1] fibArray[i - 2];}return fibArray;
}示例2分析空间复杂度是ON 示例3 计算阶乘递归Fac的空间复杂度 // 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}示例3 分析空间复杂度O(N) 示例4 计算递归斐波那契的空间复杂度 long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}示例4分析 时间复杂度是O(2^N 空间复杂度是ON 示例5 #includestdio.h
void F2()
{int b 0;printf(%p\n, b);
}void F1()
{int a 0;printf(%p\n, a);}int main()
{F1();F2();//TestSeqList1();return 0;
}F1调用的时候会开辟一块空间调用结束之后这块空间就还给操作系统了然后F2调用的时候操作系统会把这块空间给F2() 内存的申请就像是住酒店一样你申请了一块空间相当于开了一间房然后你使用完就退房了钥匙给酒店前台了(OS)。只要这间房是空的酒店前台(OS)就会把间房给其他人继续使用。
