问题
如何找到算法的时间复杂度？
在SO上发布问题之前我做了什么？
但是,我没有能够找到关于如何计算时间复杂度的明确而直接的解释.
我知道什么 ？
假设代码如下所示:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
说一个像下面这样的循环:
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i = 0; 这只会执行一次.实际计算时间i=0而不是声明.
我<N; 这将执行N + 1次
i ++; 这将被执行N次
所以这个循环所需的操作数量是
{1+(N + 1)+ N} = 2N + 2
注意:这仍然可能是错误的,因为我对计算时间复杂度的理解没有信心
我想知道什么？ …
以下嵌套循环的Big-O时间复杂度是多少:
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
System.out.println("i = " + i + " j = " + j);
}
}
它还是O(N ^ 2)吗？
什么是复杂性:
int f4(int n)
{
int i, j, k=1, count = 0;
for(i = 0; i < n; i++)
{
k *= 3;
for(j = k; j; j /= 2)
count++;
}
return count;
}
我知道它是O(n ^ 2)但你怎么计算这个？为什么不是n*log n？
问题很简单,但我找不到足够好的答案.在关于大O符号最upvoted SO问题,它说:
例如,通常基于比较操作来比较排序算法(比较两个节点以确定它们的相对排序).
现在让我们考虑一下简单的冒泡排序算法:
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
switchPlaces(...)
}
}
}
我知道最坏的情况是O(n²)最好的情况O(n),但究竟是n什么？如果我们尝试对已经排序的算法进行排序(最好的情况),我们最终什么都不做,那么为什么它仍然存在O(n)呢？我们仍在循环2个for循环,所以如果它应该是什么O(n²).n不能进行比较操作的次数,因为我们还是比较所有的元素吧？
procedure matrixvector(n:integer);
var i,j:integer;
begin
for i<-1 to n do begin
B[i] = 0;
C[i] = 0;
for j<-1 to i do
B[i]<- B[i]+ A[i,j];
for j<-n down to i+1 do
C[i]<-C[i] + A[i,j]
end
end;
我很好奇使用Big O Notation描述这个的官方方式是什么？
var prices = [100, 180, 260, 590, 40, 310, 535, 10, 5, 3];
var biggest_profit = 0;
for (var i=0; i < prices.length; i++) {
var first_price = prices[i];
for (var j=i+1; j <= prices.length; j++) {
// do something here
}
}
这有点让我失望:
j=i+1
每次我们经历i,j变得越来越短.
Big O Notation中此模式的正确名称是什么？
如果以下循环结构处于上限分析中，它是否仍然计算为 O(n^2)？我很困惑，因为内部循环依赖于外部循环，并且每次外部迭代时，内部 for 循环都会少循环一次。除了 O(n) 是什么之外，时间复杂度函数是否会是“n!.n+C”（其中 C 是常数）？我假设n！因为内循环。
for(int i=n;i>0;i--)
{
for(int j=i;j>=1;j--)
{
count++;
}
}
以下代码段的时间复杂度是多少？你能解释一下吗？
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
//print something
}
}