为code段的时间复杂度 [英] The time complexity for a code segment

问题描述

这是一个在线的笔记，我读了下面的Java code段为扭转一个字符串，它声称有二次的时间复杂度。在我看来，该for循环，因为我只是遍历s的整个长度。它是如何造成的二次的时间复杂度？

 公共静态字符串反转（String s）将
{
  字符串转=新的String（）;
  的for（int i =（s.length（） -  1）; I＆GT; = 0;我 - ）{
      REV = rev.append（s.charAt（一））;
  }
  返回rev.toString（）;
}
 

解决方案

 公共静态字符串反转（String s）将
{
  字符串转=;
  的for（int i = s.length（） -  1; I＆GT; = 0;我 - ）
  rev.append（s.charAt（我）; //＆LT; ---------这是O（n）
  返回rev.toString（）;
}
 

我复制粘贴到你的code。我不知道你在哪里得到这个，但实际上字符串没有追加方法。也许转是的的StringBuilder 或其他可追加。

From an online notes, I read the following java code snippet for reversing a string, which is claimed to have quadratic time complexity. It seems to me that the "for" loop for i just iterates the whole length of s. How does it cause a quadratic time complexity?

public static String reverse(String s)
{
  String rev = new String();
  for (int i = (s.length()-1); i>=0; i--) {
      rev = rev.append(s.charAt(i));
  }
  return rev.toString();
}

解决方案

public static String reverse(String s)
{
  String rev = " ";
  for (int i=s.length()-1; i>=0; i--)
  rev.append(s.charAt(i); // <--------- This is O(n)
  Return rev.toString();
}

I copy pasted your code. I'm not sure where you get this but actually String doesn't have append method. Maybe rev is a StringBuilder or another Appendable.

这篇关于为code段的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！