时间这个算法不断循环

-3

for(int i = 0; i < 1337; i++){ 
    printf("\n"); 
    }

是O（1），因为我们有不论n

但怎么样：

char * s = "abcdef"; 
for(int i = 0; i < 1337; i++){ 
     strlen(s); 
     }

是这样的O（N） now？请任何一位解释

来源

2017-04-13 gar

第二个例子中是否有N个？ –

以及在上述两种情况下，TC应该有什么不同？ –

现在是O（| s |）的O（1337 * | s |），如果你的意思是s是可变的。但是你的问题到底是什么，我还是不明白... – shole

如果你有一个不变的输入，算法的复杂度将总是为O（1），因为你将执行相同数量的操作。

但是，如果输入s算法，复杂度将变为O(len(s))。请注意，O(N)在这个例子中没有意义，因为您没有没有定义什么是N。

来源

2017-04-13 07:58:34

-1

它仍然是O（1），因为你仍然在循环次数不变。它不会改变，如果你改变任何给定的变量的值。

来源

2017-04-13 08:00:03 Sham3r

您需要定义什么N是。你的第一个例子是O（1），不管你如何看待它。你的第二个例子是O（N）的长度为s，因为strlen是O（N）。

来源

2017-04-13 08:00:39

谁想出了定义所有东西的想法？在大O符号中，字面上任何东西都可以作为描述符。如果我写'O（M^N）'，那么很明显复杂度被一些表示为M和N的可变部分所约束，复杂度为M^N，只有当我想详细讨论期望的值范围有助于了解“M”和“N”的起源。抽象复杂性语句不需要这么做 – grek40

@ grek40 - 不确定你的意思 - 如果你不指定什么输入/变量/等等。 N涉及到那么O（N）是相当无意义的。 –

@OliverCharlesworth在某种程度上需要有一个定义。然而，我认为在big-O的情况下，任何显示的“M，N，...”（除非另有定义）都可以被解释为表示一些线性缩放输入，这有助于表示方式的复杂性。并不是每个人都对代表性的详细映射感兴趣。现在，当我有一个线性复杂性约束时，即使不知道详细的“N”，我也可以使用任何有限次数的“O（N）”函数。 – grek40

时间这个算法不断循环

回答

相关问题