相关疑难解决方法(0)

对于没有嵌套的循环,Big O符号对于两个符号是什么？

例:

for(int i=0; i<n; i++){
   System.out.println(i);
}

for(int j=0; j<n; j++){
   System.out.println(j);
}

可能重复:
Big O的简单英文解释

我找不到足够的帮助来学习或理解O符号,以及如何了解时间或空间的复杂性.所以请建议我,我在哪里可以开始这个.它真的需要我,现在这些时间.所以请快速给我解决方案.非常感谢提前.

我们可以说,当大小为n的数组A中的所有元素相同时,堆排序的运行时间为O(n)

- >如果是这种情况,是否是O(n)最好的案例运行时间的heapsort

什么是 Theta 符号的简单英文解释？使用尽可能少的正式定义和简单的数学。

theta 表示法与 Big O 表示法有何不同？谁能用通俗的英语解释一下？

在算法分析中有怎么用？我很迷惑？

想象一下,我有一个很大的整数排序列表(> 1000项).我需要能够在此列表上执行两个操作:删除下半部分并通过插入随机整数将列表再次填充到其原始大小.因为我做了大约一百万次这些操作,所以我需要它尽可能高效.

我做的第一件事就是使用List我通过在正确的位置添加新项目进行排序的方法.虽然删除排序列表的下半部分非常容易,但插入需要相当长的时间.

我尝试实现一个跳过列表,但经过一些测试后,列表的大小似乎必须至少为10000才真正重要,否则它的表现甚至比我的正常列表更糟糕.

这就是为什么我决定使用AVL树,所以我可以更快,更快地插入项目.但问题是我不知道删除这种二叉搜索树的下半部分的任何有效方法.

我的问题是:有没有一种有效的方法来做到这一点？还有其他我可以更轻松使用的数据结构吗？

编辑

如上所述,我做了一个小测试,显示了列表,跳过列表和AVL树之间的性能差异.我在msdn:Skip list tutorial上使用本教程制作了跳过列表.AVL树来自这里:AVL树.我在dropbox上传了测试:示例.还有关于pastebin:程序.

在测试中,我在计时时为每个数据结构添加了10万个项目.在我的电脑上,列表大约需要1秒,跳过列表需要0.5秒,AVL树需要0.045秒.如果我按照我的意愿做了一百万次,那么这个列表大约需要11.5天,但AVL树只需要大约半天.这个时间差异清楚地表明了我希望它有效的原因.

给定一个字符串,找到具有相同元音和辅音数量的最长子字符串.

澄清:我不确定,我们是否可以生成一个新字符串,或者子字符串必须是原始字符串的一部分？到目前为止我有这个,

代码片段:

    Scanner scanner = new Scanner(System.in);
    String string = new String(scanner.next());
    int lengthOfString = string.length();
    int vowelCount = 0;
    int consCount = 0;

    for (int i = 0; i < lengthOfString; i++) {
        if (string.charAt(i) == 'u' || string.charAt(i) == 'e'  || string.charAt(i) == 'i'
                || string.charAt(i) == 'o' || string.charAt(i) == 'a' ) {
            vowelCount++;


        } else {

            consCount++;
        }

    }

    System.out.println(vowelCount);

编辑我得到了计数工作,但我如何创建子字符串？

我真的想知道真正的定义.我试过看书,却无法理解.

O:Big-O符号最坏的情况.
Θ:Theta表示法的平均情况.
Ω:欧米茄符号最好的情况.

为什么维基百科代表Big-O算法的速度,包括其平均,最佳和最差情况？为什么他们没有取代那些正式的关键词？

请有人解释一下:

如果文档说STL std :: vector find element performace = O(ln(n)),那是什么意思.

O(ln(n))- 什么是" O ",在哪里我可以读到这个？

在那里我可以阅读其他STL容器性能的性能

非常感谢你

我知道什么是O(n)符号,我也理解如何得到O(n),O(n ²)等符号....

• O(n)意味着我必须完成一次序列
• O(n ²)表示我有两个嵌套循环遍历序列

但是我如何得到log(N)？

PS:我知道Collections API和一些具有O(n log n)遍历时间的类.我需要一个简单的解释.

我已经阅读了一些算法书中的算法运行时,它表示为,O(n).例如,给定代码将在O(n)时间内运行以获得最佳情况并且在最坏情况下运行O(n ³).它是什么意思以及如何根据自己的代码计算它？它是否像线性时间一样,是否就像每个预定义的库函数都有自己的运行时一样,在调用它之前应该记住它？谢谢...