leetcode--复杂度
2021/12/8 23:17:03
本文主要是介绍leetcode--复杂度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
时间复杂度
cookbook上的几个特殊例子分析
Example 1
void hello (int n){ for( int sz = 1 ; sz < n ; sz += sz) for( int i = 1 ; i < n ; i ++) cout << "Hello" << endl; }
第一个循环的条件是”sz+=sz",相当于递归,区间段长度为sz。
时间复杂度为:O(nlogn)
Example 2
bool isPrime (int n){ for( int x = 2 ; x * x <= n ; x ++ ) if( n % x == 0) return false; return true; }
循环条件相当于x*2=n。
时间复杂度为:O(sqrt(n))
例1和例2说明,判断时间复杂度需要具体看循环条件是什么,而不能直接看循环结构。
Example 3
有一个字符串数组,将数组中的每一个字符串按照字母序排序,之后再将整个字符串数组按照字典序排序。两步操作的整体时间复杂度是多少呢?
1. 对每一个字符串排序时,一般用快排、归并等算法排。假设字符串最长为s,则该步骤的时间复杂度为:O(slogs)。
2. 对字符串组排序时,也一般用快排、归并等算法排。假设数组长度为n,则该步骤的时间复杂度为:O(nlogn)。
总的时间复杂度为:O(nslog(s+n)
空间复杂度
Example 1
int sum( int n ){ assert( n >= 0 ) int ret = 0; for ( int i = 0 ; i <= n ; i++) ret += i; return ret; }
空间复杂度为:O(1)
Example 2
int sum( int n ){ assert( n >= 0 ) if ( n == 0 ) return 0; return n + sum( n - 1); }
递归调用sum函数,相当于n+n-1+n-2+n-3+....+1。
空间复杂度为:O(n)
递归的时间复杂度
主定理、递归树、假设验证法
这篇关于leetcode--复杂度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享