前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法(一) 简单例子理解时间复杂度和空间复杂度

数据结构与算法(一) 简单例子理解时间复杂度和空间复杂度

作者头像
老沙
发布2019-09-28 13:17:53
4080
发布2019-09-28 13:17:53
举报
文章被收录于专栏:老沙课堂

用O 标识时间复杂度 以及空间复杂度 简单来说就是执行代码的次数

我们分析下下面的时间复杂度
代码语言:javascript
复制
public static void test(int n) {
  // i = 0 执行1次  i < n 执行n次 i++ 执行n次
  for (int i = 0; i < n; i++) {
      // j = 0 执行n次  j < n 执行n^2次 j++ 执行n^2次
    for (int j = 0; j < n; j++) {
      //执行n^2次
      System.out.println("123");
    }
  }
}
时间复杂度计算

所以总的时间为1 + n + n + n + n^2 + n^2 + n^2 = 1 +3n +3n^2 由于计算时间复杂度可以省略常数,系数以及低阶 所以这个算法的时间复杂度为O(n^2)

代码语言:javascript
复制
public static void test2(int n) {
 // i = 0 执行1次  i < n 执行n次 i++ 执行n次
  for (int i = 0; i < n; i++) {
    //j = 0 执行n次   j < i 执行 0 + 1 + 2 + 3 +...+ (i - 1)次  j++执行 0 + 1 + 2 + 3 +...+ (i - 1)次
    for (int j = 0; j < i; j++) {
      //执行 0 + 1 + 2 + 3 +...+ (i - 1)次
      System.out.println("123");
    }
  }
}
时间复杂度计算

总时间为 1 + n + n + n + (0 + 1 + 2 + 3 +...+ (i - 1)) + (0 + 1 + 2 + 3 +...+ (i - 1)) + (0 + 1 + 2 + 3 +...+ (i - 1)) 由于i = n - 1 所以

1 + n + n + n + (0 + 1 + 2 + 3 +...+ (n - 2)) + (0 + 1 + 2 + 3 +...+ (n - 2)) + (0 + 1 + 2 + 3 +...+ (n - 2)) // 0 + 1 + 2 + 3 +...+ (n - 2) = (0 + n -2) * n/2 = n^2/2 -n 所以原式为1 + n + n + n + 3(n^2/2 - n) = n^2/2 + 1 所以时间复杂度为O(n^2)

代码语言:javascript
复制
public static void test3(int n) {
   // i = 0 执行1次  i < n 执行n次 i++ 执行n次
  for (int i = 0; i < n; i++) {
    //j = 0 执行n次
		// j + = j等价于 j = j * 2  所以执行次数就是 2^j < n 因为2^j = n  j = log2^n
    // 因为log5^n = log2^5 *long5^n  所以一般我们忽略底部系数 次数为log n
    // 所以j < n 和 j += j 的执行次数为n * logn
    for (int j = 0; j < n; j += j) {
      // 执行次数为n * logn
      System.out.println("123");
    }
  }
}
时间复杂度计算

// 总的执行次数为 1 + n + n +n + n *logn + n * logn + n * logn = 1 + 3n + 3nlogn //所以时间复杂度为nlogn

常见的复杂度

举个? 斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)

代码语言:javascript
复制
	public static int fib(int n) {
		if(n <= 1 ) return n;
		return fib(n - 1) + fib(n - 2);
	}

我们算一下时间复杂度 举个例子 如果我们输入的是4 我们看一下这个时间复杂度是多少

2^0 + 2^1 + 2^2 + ...2^n)= 2^(n-1) - 1 = 0.5*2^n

所以这个时间复杂度为2^n

代码语言:javascript
复制
public static int fib2(int n) {
  if (n <= 1) {
    return n;
  }
  // 1
  int first = 0;
  // 1
  int second = 1;
  // int i > 1次  i的判断 -> n-1次  i++ -> n-1次
  for (int i = 0; i < n - 1; i++) {
    int  sum = first + second;
    first = second;
    second = sum;
  }
  return second;
}

而下面这个算法就一个for循环 可见时间复杂度为n

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-09-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 老沙说点事 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 我们分析下下面的时间复杂度
  • 时间复杂度计算
  • 时间复杂度计算
  • 时间复杂度计算
  • 常见的复杂度
  • 举个? 斐波那契数列
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档