专栏首页包子铺里聊ITHow to calculate “hard” runtime complexity?

How to calculate “hard” runtime complexity?

在技术面试中,准确说出一个解法的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..

。。。

本文分享自微信公众号 - 包子铺里聊IT(baozitraining)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2014-08-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 码农们,你不能没有的职场情商

    包子君听到Conscious Business这个词是在三番startup mixer活动上听到Fred Kofman的演讲中,后来听Facebook COO...

    包子面试培训
  • 劳动最光荣!Double Letter Problem from TopCoder

    包子IT面试培训 助你拿到理想的offer! 这是TopCoder上面一道比较简单的250分的题目,非常适合作为面试的第一道热身题目,考察了面试者对于基本的数据...

    包子面试培训
  • Leetcode 208 solution: Implement Trie (Prefix Tree)

    https://blog.baozitraining.org/2019/04/leetcode-solution-208-implement-trie.html

    包子面试培训
  • 如何计算算法的复杂度

    这段伪代码运行了多少次呢! 1次 ,时间时间复杂度为O(1):常数复杂度/常数阶。

    营琪
  • Big O notation 算法复杂度计算方法

    Big O notation大零符号一般用于描述算法的复杂程度,比如执行的时间或占用内存(磁盘)的空间等,特指最坏时的情形。

    栋先生
  • 你应该收藏起来的算法复杂度速查表

    这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 OBig-O 复杂度。我之前在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣,以便...

    用户2617681
  • ResNet论文翻译——中文版

    Deep Residual Learning for Image Recognition 摘要 更深的神经网络更难训练。我们提出了一种残差学习框架来减轻网络训...

    Tyan
  • 给 RecyclerView 加上折叠的效果

    RecyclerView 有很高的自由度,可以说只有想不到没有做不到,真是越用越喜欢。这次用超简单的方法,让 RecyclerView 带上折叠的效果。

    NanBox
  • 算法面试指南

    算法是技术面试的重要组成部分,尤其是在国内外的大厂中。本文将为你介绍在面试中需要了解的常见算法以及提高它们效率的方法(这是面试中常见的问题),最后会为你提供一些...

    疯狂的技术宅
  • 谈谈关于Exception 和 Error 的理解

    世界上存在永远不会出现错误的程序吗?也许这只会出现在程序员的梦中。随着软件的诞生,异常就如影随形的围绕着我们,所以,只有正确处理好程序的意外情况,才能有效的避免...

    cxuan

扫码关注云+社区

领取腾讯云代金券