我正在学习Big-O,虽然我开始理解一些东西,但我仍然不能正确地衡量算法的Big-O。我有一个代码:
int n = 10;
int count = 0;
int k = 0;
for (int i = 1; i < n; i++)
{
for (int p = 200; p > 2*i; p--)
{
int j = i;
while (j < n)
{
do
{
count++;
k = count * j;
} while (k > j);
我试图开发一种解决方案,将O(n^2)或O(n*m)算法的时间复杂度降低为O(n)或O(n+m)算法。例如:
let arr = [[1, 2], [1, 2, 3], [1, 2, 3, 4, 5, 6, 7, 8]];
let x = 0;
let len = getArrayMaxLength (arr) //Get the maximum length of a 2d array which in this example is 8.
for (let i = 0; i < len && x < arr.length; ++i
我试图理解Big-O表示法,所以我使用while循环制作了自己的O(n)示例,因为我发现while循环在Big O表示法中理解起来有点混乱。我定义了一个名为linear_example的函数,它接受一个列表,例如is python:
所以我的代码是:
def linear_example (l):
n =10
while n>1:
n -= 1
for i in l:
print(i)
我的想法是for循环中的代码以O(1)的恒定时间运行,而while循环中的代码以O(n)时间运行。因此,它的结果是O(1)+O(n)
当我回顾数据结构和算法的大O符号时,当不同的源将从链表中删除节点的时间复杂度设置为O(n)与O(1)时,我感到困惑。例如,big O cheat sheet在删除节点时放置O(1),而我认为删除节点的时间为O(n),因为您必须首先找到该节点,然后将其删除。 所以我的问题是,O(1)的时间复杂度是否只是假设删除操作本身,而没有考虑到必须首先找到节点?让我们假设要删除的节点在列表中的任何位置,而不仅仅是在列表的前端或末尾。 我复习了以下问题,但它们没有回答我的问题: big O notation for removing an element from a linked list Big-O s
以下代码的时间复杂度是多少?
def func(n):
for _ in range(n):
if n == 4:
for _ in range(n):
<do something>
对于一个特定的输入(n = 4),它将只是O(n^2),但对于所有其他输入,它将是O(n)。在这种情况下,最坏的情况显然是O(n^2),但我的讲师说O(n)是正确的答案。如果"big-Oh“符号表示的是最坏的情况,为什么它不是O(n^2)?
另一个是:
def func2(n):
for _ in rang
我对big-o还很陌生,我想弄清楚这一小段代码的大o运行时间是多少。我知道通常情况下,如果有,但是整个数组的事情会改变什么吗?我很困惑,所以任何一点的输入都是很好的。提前感谢!
public apple(int n)
{
int n = 0;
int apple = 0;
a = apple + n;
}
void intFunction (int n, int value)
{
int b,c;
for (int j = 4; j < n; j++) {
for (int i = 0; i < j; i++) {
b *= val;
for (int k = 0; k < n; ++k)
c += b;
}
}
}
我刚学会了Big-O的概念。所以对于这段代码,据我所知,外部循环运行时间是n,第二个内部循环运
我正在尝试找出这个算法的时间复杂度(Big-Θ): Recursion(n):
while n > 1:
n = floor(n/2)
Recursion(n) 通过考虑最坏的情况,即当n是2的幂时,我找到了O(n)的一个上界。 然而,我很难找到一个下限(大Ω)。我的直觉是这也是Ω(n),但我不确定如何用floor函数来表示它。 有什么建议吗?谢谢! 编辑:我最不相信的是T(n/2)等于T(floor(n/2))。如何证明这个算法呢?
我已经开始学习Big O符号和分析时间复杂性,并尝试摆弄一些代码来尝试理解它的时间复杂性。这是我的其中一行代码,但我似乎不能计算出求和方法的时间复杂度是多少?我估计它是o(n^3),但我的朋友说它应该是o(n^2)。关于正确答案是什么,有什么见解吗? public static double sum(double[] array)
{
double sum = 0.0;
for(int k = 0; k < size(array); k++)
sum = sum + get(array, k);
return sum;
}
public static
使用计时器测试验证代码的运行时复杂性是明智的吗?
例如:
x=very large input
timer start
foo(x)
timer end
print time
如果时间是0秒,那就意味着foo运行在O(n)或更少,如果计时器是30-60秒,这意味着运行时必须大于O(n)?
一般来说,一个函数需要更多的时间吗?这意味着它的运行时复杂度更大吗?
如果给定一个函数sorted,如果列表以O(N)的形式运行,该函数将返回True,您将如何描述这种排序的运行时间:
def sort(l):
while not sorted(l): random.shuffle(l)
假设洗牌是完全随机的。
这会用big-O符号来写吗?或者,有没有其他方法来对随机成分的算法进行分类?
我必须分析这个循环和其他循环,并使用Big-O表示法确定它的运行时间。
for ( int i = 0; i < n; i += 4 )
for ( int j = 0; j < n; j++ )
for ( int k = 1; k < j*j; k *= 2 )`
这是我到目前为止所知道的:
for ( int i = 0; i < n; i += 4 ) = n
for ( int j = 0; j < n; j++ ) = n
for ( int k = 1; k < j*j; k *= 2 ) = log^2 n
现在我
所以我很难理解Big O Notation,我正在寻找一些例子来更好地理解它。现在让我们看一下下面的代码: `public static void main(String[] args)` {
int N = 4;
int sum = 0;
for (int i = 1; i < N; i = i*2)
{
for (int j = 1; j < N; j++)
{
sum++;
我写了一个关于幂集的算法,写成P(a)。正在学习算法的时间复杂性(Big-O),如果我错了,请纠正我。
算法:
function powerSet(int[] a ){
ArrayList pw = new ArrayList();
pw.add(" ");
for (int i = 1; i <= a.length; i++) //O(n){
ArrayList<String> tmp = new ArrayList<String>();
for (String e : pw)//O(n) {
我有以下代码: for each nodeG in Graph
for each nodeS in subset
path(nodeG, nodeS) // using dijkstra that in the best has O(V lg V + E);
end
end 每次执行主循环时,都会从队列中提取一个顶点。假设图中有V个顶点,队列可能包含O(V)个顶点。假设优先级队列的堆实现,每个pop操作花费O(lg V)时间。因此,执行主循环本身所需的总时间为O(V,lg,V)。此外,我们必须考虑在函数expand中花费的时间,该函数将函数handle_edge应用