首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >How to calculate “hard” runtime complexity?

How to calculate “hard” runtime complexity?

作者头像
包子面试培训
发布2018-04-19 10:42:07
8430
发布2018-04-19 10:42:07
举报
文章被收录于专栏:包子铺里聊IT包子铺里聊IT

在技术面试中,准确说出一个解法的runtime complexity(算法时间复杂度)是一个非常重要的点。考虑到对于算法时间复杂度的理解是CS领域的基础,因此这类问题,回答对了往往那不加分,但是回答错误往往是致命的,因此大家不能掉以轻心。

Note: 本篇只讨论算法的时间复杂度,不涉及算法的空间复杂度。:)

对于基本的算法复杂度分析,Big O notation是必须要掌握的,详情请看wikipedia相关资料:http://en.wikipedia.org/wiki/Big_O_notation 。 简单的说,Big O描述了当输入(input)的复杂度线性增长时,一个算法的计算时间复杂度的增长变化。举个例子,如果我们说一个算法的是时间复杂度是O(n),那么意味着当该算法的输入线形增长时,其计算时间也成线性增长。

『简单的时间复杂度计算』

大部分非递归算法的时间复杂度计算比较简单,一句话简单表述,就是数有多少层嵌套循环即可,(每个循环的次数和算法的输入n相关)。比如一个问题描述『求n个int数中的最大数』,那么解法中需要用一次循环来遍历所有input(即n个数),然后返回结果。由于只需要一层循环,那么该算法时间复杂度为O(n).

『相对复杂的时间复杂度计算』

当一个算法中既包含循环(loop)又包涵递归(recursive)的时候,算时间复杂度可能需要动动脑筋。这部分也是本章重点。:)

用最近的一道高频题做例子:

Problem:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return one such possible sentences.

s = "catsanddog", dict = ["cat", "and", "sand", "dog"], return “cats and dog";

(Leetcode word break II 简化版)

Clarification

Q: What to return if s can’t be splitted into words in dict? A: Return NULL;

Q: What if there are multiple ways of splitting s? A: Return one split solution is fine;

Q: What if S is null/empty string? A: Return NULL;

So on and so forth..

。。。

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

本文分享自 包子铺里聊IT 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 在技术面试中,准确说出一个解法的runtime complexity(算法时间复杂度)是一个非常重要的点。考虑到对于算法时间复杂度的理解是CS领域的基础,因此这类问题,回答对了往往那不加分,但是回答错误往往是致命的,因此大家不能掉以轻心。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档