这段简单的代码的复杂性是多少?

2024-02-19

I'm pasting this text from an ebook I have. It says the complexity if O(n2) and also gives an explanation for it, but I fail to see how.

问题:这段代码的运行时间是多少?

public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}

书中给出的答案是:

O(n2), where n is the number of letters in sentence. Here’s why: each time you append a string to sentence, you create a copy of sentence and run through all the letters in sentence to copy them over If you have to iterate through up to n characters each time in the loop, and you’re looping at least n times, that gives you an O(n2) run time. Ouch!

有人可以更清楚地解释这个答案吗?


这似乎是一个误导的问题,因为我刚才正好读到那本书。书中这部分文字是错字!这是上下文:

=================================================== =================

问题:这段代码的运行时间是多少?

1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }

Answer: O(n2), where n is the number of letters in sentence. Here’s why: each time you append a string to sentence, you create a copy of sentence and run through all the letters in sentence to copy them over. If you have to iterate through up to n characters each time in the loop, and you’re looping at least n times, that gives you an O(n2) run time. Ouch! With StringBuffer (or StringBuilder) can help you avoid this problem.

1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }

=================================================== ===================

Have you noticed that the author messed it up? The O(n2) solution she mentioned (the first one) was exactly the same as the 'optimized' one (the latter). So, my conclusion is that the author was trying to render something else, such as always copying the old sentence to a new buffer when appending every next string, as the example of an O(n2) algorithm. StringBuffer should not be so silly, as the author also mentioned 'With StringBuffer (or StringBuilder) can help you avoid this problem'.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

这段简单的代码的复杂性是多少? 的相关文章

  • 春天。使用java配置解决循环依赖而不使用@Autowired

    我有循环依赖和java配置 虽然使用 xml 配置解决它非常简单 但如果没有 Autowired 我无法使用 java 配置解决它 豆子 public class A private B b public B getB return b p
  • 我可以为 Spring Boot 应用程序创建多个入口点吗?

    In 春季启动 需要指定一个主类 它是应用程序的入口点 通常 这是一个具有标准 main 方法的简单类 如下所示 SpringBootApplication public class MySpringApplication public s
  • 在 Java 中将系统属性设置为 Null

    在我的单元测试中 我需要将 workingDir 系统属性设置为 Null 但我不能这样做 因为它给了我 NullPointerException System setProperty workingDir null 我该怎么做 您不能将属
  • 如何解析比 Java 中 NumberFormat 更严格的数字?

    我正在验证表单中的用户输入 我解析输入NumberFormat http docs oracle com javase 7 docs api java text NumberFormat html 但它是邪恶的 几乎允许任何事情 有没有办法
  • 在 Java 和 C 中在运行时调用名为“string”的方法

    我们如何调用名称为的方法string在运行时 谁能告诉我如何在 Java 和 C 中做到这一点 在java中可以通过反射api来完成 看一下Class getMethod String methodName Class parameterT
  • Eclipse 说“更新 Android Developer Toolkit”

    我不知何故弄乱了我的 Eclipse 和 Android 设置 我不知道如何修复它 问题症状如下 在 首选项 gt Android 中 我尝试选择 android sdk linux 的位置 选择时出现错误 此 Android SDK 需要
  • 将对象列表传递给 Freemarker 然后循环

    我已经熟悉了 FreeMarker 一个 Java 模板引擎 我已经能够通过哈希映射将对象传递给模板引擎了 这样就可以了 但是 一旦我尝试将任何类型的多个对象集传递给 FreeMarker 它就会给我一个 freemarker templa
  • 使用java在mysql中插入带有\\的文件路径

    我正在使用java制作一个独立的应用程序 并且我需要插入用户从文件选择器中选择的图像的路径 我正在获取文件的路径 但是当我将其存储在数据库 mysql 中时 它不会存储 所以当我检索该路径时 该文件不会显示 如何存储文件的路径 这样就可以使
  • 归并排序究竟进行了多少次比较?

    我读到 在实践中 快速排序比合并排序快得多 其原因是隐藏常量 那么 随机快速排序复杂度的解是2nlnn 1 39nlogn 这意味着快速排序中的常数是1 39 但是合并排序呢 归并排序中的常数是什么 让我们看看能否解决这个问题 在合并排序中
  • Maven:缺少工件 org.springframework:spring:jar:4.2.6

    我在 SpringToolSuite 中有一个动态 Web 项目 它被转换为 Maven 项目 我遇到问题 缺少工件 org springframework spring jar 4 2 6 我已经尝试清理 重建和运行该项目 它给 读取文件
  • 用 Java 捕获扬声器输出

    使用Java可以捕获扬声器输出吗 此输出不是由我的程序生成的 而是由其他正在运行的应用程序生成的 这可以用 Java 完成还是我需要求助于 C C 我有一个基于 Java 的应用程序 使用过的爪哇声音 https stackoverflow
  • Spark toLocalIterator 和迭代器方法之间的区别

    在编写 Spark 程序时我遇到了这个toLocalIterator 方法 之前我只使用iterator method 如果有人曾经使用过这种方法 请点亮 我在使用时遇到foreach and foreachPartitionSpark程序
  • 将 Class 对象转换为字节

    如果我有一个Class http java sun com j2se 1 5 0 docs api java lang Class html在运行时实例 我可以获得它的 byte 表示形式吗 我感兴趣的字节将在类文件格式 http java
  • 如何根据服务器/环境动态加载服务器配置?

    目前 我设置了 Maven 配置文件 以便能够为不同的环境 开发 演示 暂存 生产等 部署我的项目 并且它工作得很好 但问题是 对于我拥有的每个模块 Web 应用程序 我需要复制 粘贴此配置文件 它们都是属性文件 当我需要更改环境 服务器配
  • Java可以进行进程监控吗?

    是否可以用Java编写一个在托盘中运行的应用程序 并且当启动某个应用程序时 它可以检测到它 我想对某些程序执行此操作 以了解我每周使用它们多长时间 我是 Java 新手 所以我不知道 Java 是否是最适合此操作的语言 或者它是否具有对操作
  • 如何避免连续“重置偏移量”和“寻找最新偏移量”?

    我正在尝试遵循本指南 https spark apache org docs latest structed streaming kafka integration html https spark apache org docs late
  • LinkedBlockingQueue 抛出 InterruptedException

    我有这段代码 ALinkedBlockingQueue应该只抛出一个Exception如果在等待添加到队列时被中断 但这个队列是无限的 所以它应该尽快添加 为什么我的关闭方法会抛出一个InterruptedException private
  • @JsonCreator '无法找到具有名称的创建者属性',即使使用ignoreUnknown = true

    我有以下课程 JsonIgnoreProperties ignoreUnknown true public class Topic private List
  • Ant 类路径和 junit.jar

    我有一个 build xml 它允许我运行 junit 测试 这是相关部分
  • 如何使用 JRE 部署 JavaFX 11 桌面应用程序

    我有一个 JavaFX JDK 8 桌面业务应用程序 它使用 Java Web Start 进行部署 用户安装了 Java 8 只需访问 URL 我的 AWS Linux 服务器上的公共 URL 即可下载 启动应用程序 使用 Web Sta

随机推荐