我正在研究并试图实现一些算法.我正在尝试理解Big O表示法,我无法弄清楚下面算法的Big O复杂性:
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
if (a == 0)
common=b;
else
common=a;
可能重复:
Big O的简单英文解释
亲爱的大家,
当我阅读有关某些算法的信息时,偶尔会遇到算法性能信息,例如:O(1),O(n),O(n ^ 2)等.
我是否可以获得有关如何翻译和理解这些性能数据的解释？什么样的O(n)变体可用,它们在实践中意味着什么？
谢谢.
可能重复:
Big O的简单英文解释
我需要弄清楚O(n)以下内容:
f(n) = 10n^2 + 10n + 20
我能想到的只是50,而且我太尴尬了,不知道我是怎么想出来的.
有人可以解释它意味着什么以及我应该如何计算它f(n)？
你能解释是什么让算法成为O(log n)吗？
如果您能用简单的代码展示它,我将不胜感激.
谢谢
我正在将二进制搜索树作为一项任务.
当我尝试添加1,000,000个元素时,我遇到了问题.
插入15,000个元素后我收到错误:
线程"main"中的异常java.lang.StackOverflowError
我的代码有问题我无法找到我做错的地方.
public class BinarytreeInsert {
public static void main(String[] args) {
new BinarytreeInsert().run();
}
static class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
}
public void run() {
Node rootnode = new Node(25);
System.out.println("Building tree with root value " + rootnode.value);
System.out.println("=================================");
for(int i = 0 ; i<1_000_000;i++)
insert(rootnode, i);
}
public void insert(Node node, int value) {
if (value < node.value) {
if (node.left != null) …Arrays.binarySearch()很简单，从性能角度来看，使用与使用迭代循环（遍历数组中的所有项目 - 线性搜索）来查找 Array 或 ArrayList 中的值相比如何？最终用户是否能够看到使用其中任何一个的任何延迟？
还有在某些特定情况下一种方法比另一种方法更好吗？
我在哪里可以学习编程算法(java等),因为当我搜索排列,紊乱,排序等程序时,我总能找到数学算法.
示例:计算紊乱
由此,得出以下关系:
!n = (n - 1) (!(n-1) + !(n-2)).\,
where !n, known as the subfactorial, represents the number of derangements, with the starting values !0 = 1 and !1 = 0.
Notice that this same recurrence formula also works for factorials with different starting values. That is 0! = 1, 1! = 1 and
n! = (n - 1) ((n-1)! + (n-2)!)\,
which is helpful in proving the limit relationship with e below.
Also, the following formulae …我试图了解如果内部循环不是从0开始,而是1,2,3或更多,那么big-o符号是否会改变.
例如,它改变了这个内部for循环从3开始的任何东西,还是大的o仍然是n平方？
for(int i = 0; i < n; i++)
for(int j = 3; j < n; j++)
当我在它的时候,我不妨问一下,如果i或j在每次迭代中增加3,它是否会有所不同.谢谢你的帮助!
我对Big(O)符号感到困惑.Big(O)机器是独立的还是机器独立的？(在我们运行算法的计算机中的机器)在i3处理器和i7处理器中使用快速排序对1000个数字进行排序是否相同？在计算时间复杂度时,为什么我们不考虑机器及其处理器速度？我是这个东西的初学者.
我是时间复杂度分析的新手...
如果有人能告诉我这是否是二次的，我将不胜感激。而且如果有更简单的方法可以使它成为o(1)。
public class PrimeNumbers {
public boolean isPrime(int n) {
boolean retValue = true;
for (int i = 2; i < n; i++) {
if (n % 2 == 0) {
retValue = false;
}
}
return retValue;
}
}
如果有人可以分解它为什么是这样，它肯定会帮助我学习。:)
非常感谢！
问题:哪个复杂性有我的功能？以及如何找到算法的时间复杂度？
该函数检查给定的int数组是否已排序.
我的代码:
public static boolean isSorted(double d[]){
boolean sortedAscending = true;
boolean sortedDescending = true;
boolean bool = false;
for (int i = 0; i < d.length-1; i++) {
if(d[i] > d[i+1] && sortedAscending){
sortedAscending = false;
if(bool){
break;
}
bool = true;
}
else if(d[i] < d[i+1]&& sortedDescending){
sortedDescending = false;
if(bool){
break;
}
bool = true;
}
}
return sortedAscending || sortedDescending;
}
为什么我们只采用Big Oh表示法的最高次多项式.我知道我们可以删除常数,因为它们对于非常高的'n'值无关紧要.
但是,假设算法需要(nlogn + n)时间,那么为什么我们在这种情况下忽略'n'.而大哦出来是O(nlogn).
Big Oh必须是算法所用时间的上限.那么,不应该是(nlogn + n),即使是非常高的n值？
据我了解，乘法的复杂度顺序是二次的，因此，如果将两个1位数字相乘将有1个运算，两个2位数字相加将有4个运算，两个3位数字9个运算等等上。
我想通过定时执行将两个数字相乘的程序来查看这种复杂性。出乎意料的是，无论数字的大小如何，执行时间都是相同的。
import time
num1 = 135
num2 = 342
start = time.time()
total = num1 * num2
finish = time.time()
elapsed = finish - start
print elapsed
因此，结果是9.53674316406e-07我将两个3位数或两个30位数相乘。
我误会什么？