标签: time-complexity

由于我正在研究时间复杂性,我一直在搜索oracle Java类库,以了解列表,地图和类中使用的一些标准方法的时间复杂性.(更具体地说,ArrayList,HashSet和HashMap)

现在,在查看HashMap javadoc页面时,他们只是真正谈论get()和put()方法.

我仍然需要知道的方法是:

remove(Object o)
size()
values()

我认为这remove()将是相同的复杂性get(),O(1)假设我们没有以相同散列码,等等等等,一个巨大的HashMap ...

因为size()我也假设O(1),因为HashSet也没有顺序,所以有一个size()复杂的方法O(1).

我不知道的是values()- 我不确定这个方法是否会以某种方式"复制"HashMap,给出时间复杂度O(1),或者是否必须迭代HashMap,使复杂性等于数量存储在HashMap中的元素.

谢谢.

有一种以上的解决方案可以找到给定数字中的数字位数.

例如:

方法1:

int findn(int num)
{
    char snum[100];
    sprintf(snum, "%d", num);
    return strlen(snum);
}

方法2:

int findn(int num)
{
    if (num == 0) return 1;
    int n = 0;
    while(num) {
        num /= 10;
        n++;
    }
    return n;
}

方法-3:

int findn(int num)
{
    /* math.h included */
    return (int) log10(num) + 1;
}

问题是 - 什么是最有效的方法？我知道方法-2 O(n)但是方法1和方法3怎么样？如何找到库函数的运行时复杂性？

我有一系列问题需要反馈和答案.我将评论我的想法,这不是一项家庭作业,而是为我的考试做准备.

我的主要问题是确定不同情况下循环的迭代.怎么会尝试解决这个问题？

评估运行时间.

Q2.

 for(int i =0 ; i < =n ; i++) // runs n times
   for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
      if (j % i == 0)
         for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
            sum++;

正确答案:N×N2×N = O(N ^ 4)

对于以下问题,我没有正确的答案.

Q3.一个)

     int x=0; //constant
     for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
         x=x+2*i;

我的答案:O(n)

b)为简单起见,假设n = 3 …

什么是创建一个复杂线索单词列表的,什么是该线索寻找另一组字的复杂性？当我有哈希表时,我应该使用trie进行字符串搜索吗？

考虑一下这段代码:

public String joinWords(String[] words) {
    String sentence = "";
    for(String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}

在每个串联上创建一个新的字符串副本,以便整体复杂化O(n^2).幸运的是,在Java中,我们可以使用a来解决这个问题,每个附加StringBuffer都有O(1)复杂性,然后整体复杂性就是这样O(n).

虽然在C++中,std::string::append()有复杂性O(n),而且我不清楚它的复杂性stringstream.

在C++中,是否存在StringBuffer具有相同复杂性的方法？

对于字符串A ="abcd",则答案应为{a,ab,abc,abcd,b,bc,bcd,c,cd,d}

要查找我使用以下方法的所有子字符串

{a,ab,abc,abcd,b,bc,bcd,c,cd,d} 

但根据我的理解,复杂性是O(N ^ 2).我们可以加快速度吗？我提到了以前的问题,后缀树http://allisons.org/ll/AlgDS/Tree/Suffix/有链接,但它似乎没有解决我的问题....我从后缀树得到的输出是{1: abcd 2:bcd 3:cd 4:d}任何人都可以帮我找出最快的方法吗？像线性时间的东西？

我一直在谷歌搜索过去2个小时,我找不到PHP内置函数时间和空间复杂性的列表.我有isAnagramOfPalindrome问题要解决以下最大允许的复杂性:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

其中N是输入字符串长度.这是我最简单的解决方案,但我不知道它是否在复杂性限制范围内.

class Solution { 

    // Function to determine if the input string can make a palindrome by rearranging it
    static public function isAnagramOfPalindrome($S) {

        // here I am counting how many characters have odd number of occurrences
        $odds = count(array_filter(count_chars($S, 1), function($var) {
            return($var & 1);
        }));
        // If the string length is odd, then a palindrome …

给定一组数字,生成所有唯一对.

例如,给定[ 1, 2, 3, 4, 5 ]唯一的数字对将是:

(1, 2), (1, 3), (1, 4), (1, 5)

(2, 3), (2, 4), (2, 5)

(3, 4), (3, 5)

(4, 5)

我的解决方案如下:

int[] numbers = new int[] { 1, 2, 3, 4, 5 };
HashSet<Pair> pairs = new HashSet<Pair>();

for(int i = 0; i < numbers.Length; i++)
{
    for(int j = i + 1, j < numbers.Length; j++)
    {
        pairs.Add(new Pair(numbers[i], numbers[j]));
    }
}

我认为时间复杂度看起来像O(n ² - 1)减去1,因为迭代j总是比1短 …

Google编程面试中提到了这个问题.我想到了两种相同的方法:

1. 找到所有长度的子序列.这样做的同时计算两个元素的和,并检查它是否等于k.如果是的话,打印是,否则继续搜索.这是一种蛮力的方法.

2. 以非递减顺序对数组进行排序.然后从右端开始遍历数组.假设我们有排序数组{3,5,7,10},我们希望总和为17.我们将从元素10开始,索引= 3,让我们用'j'表示索引.然后包括当前元素并计算required_sum = sum - current_element.之后,我们可以在数组[0-(j-1)]中执行二进制或三进制搜索,以查找是否存在其值等于required_sum的元素.如果我们找到这样一个元素,我们可以打破,因为我们找到了长度为2的子序列,其总和是给定的总和.如果我们没有找到任何这样的元素,那么减小j的索引并重复上述步骤以得到长度=长度为1的子阵列,即在这种情况下通过排除索引3处的元素.

在这里,我们认为数组可能有负整数和正整数.

你能提出比这更好的解决方案吗？DP解决方案可能吗？一种可以进一步降低时间复杂度的解决方案.

这个问题一直困扰着我的脑海......

假设我有一个项目列表和它们的等价关系,并且比较两个项目需要恒定的时间.我想返回项目的分区,例如链接列表列表,每个列表包含所有等效项目.

这样做的一种方法是将等价扩展到项目的排序并对它们进行排序(使用排序算法); 那么所有等价物品都会相邻.

但它可以比排序更有效地完成吗？这个问题的时间复杂度是否低于排序？如果没有,为什么不呢？