Анализ алгоритмов :Правильно ли я анализирую эти алгоритмы? Как подходить к подобным проблемам [закрыто]

Этот вопрос вряд ли поможет будущим посетителям; это относится только к небольшой географической области, определенному моменту времени или чрезвычайно узкой ситуации, которая обычно не применима к всемирной аудитории Интернета. Чтобы получить более широкое применение этому вопросу, посетите справочный центр .

Закрыт 7 лет назад .

  x = 25;
    for (int i = 0; i < myArray.length; i++)
    {
        if (myArray[i] == x)
            System.out.println("found!");
    }

Я думаю, что это O (n ).

for (int r = 0; r < 10000; r++)
    for (int c = 0; c < 10000; c++)
        if (c % r == 0)
            System.out.println("blah!");

Я думаю, что это O (1 ), потому что для любого ввода n он будет выполняться 10000 *10000 раз. Не уверен, что это правильно.

a = 0
for (int i = 0; i < k; i++)
{
    for (int j = 0; j < i; j++)
        a++;
}

Я думаю, что это O (i *k ). Я действительно не знаю, как подходить к таким проблемам, когда на внутренний цикл влияют переменные, увеличивающиеся во внешнем цикле. Некоторые ключевые идеи здесь будут высоко оценены. Внешний цикл выполняется k раз, а внутренний цикл выполняется 1 + 2 + 3 +... + k раз. Таким образом, эта сумма должна быть (k/2)*(k+1 ), что будет порядка k^2. Так будет ли на самом деле O (k^3 )? Это кажется слишком большим. Опять же, не знаю, как к этому подступиться.

int key = 0;    //key may be any value
int first = 0;
int last = intArray.length-1;;
int mid = 0;
boolean found = false;

while( (!found) && (first <= last) )
{
    mid = (first + last) / 2;

    if(key == intArray[mid]) 
        found = true;
    if(key < intArray[mid])
        last = mid - 1;
    if(key > intArray[mid]) 
        first = mid + 1;
}

Это, я думаю, O (log n ). Но я пришел к такому выводу, потому что я считаю, что это бинарный поиск, и я знаю из чтения, что время выполнения составляет O (log n ).Я думаю, это потому, что вы делите размер ввода на 2 для каждой итерации цикла. Но я не знаю, является ли это правильным рассуждением или как подойти к подобным алгоритмам, которые я не видел, и быть в состоянии сделать вывод, что они работают в логарифмическом времени более проверяемым или формальным способом.

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

Я смущен этим. Внешний цикл выполняется n раз. И внутренний цикл for работает n + (n -1 )+ (n -2 )+... (n -k )+ 1 раз? Так это O (n^3 )??

задан Franck Dernoncourt 13 July 2012 в 20:41

0 ответов

Другие вопросы по тегам:

algorithm big-o time-complexity c++

Анализ алгоритмов :Правильно ли я анализирую эти алгоритмы? Как подходить к подобным проблемам [закрыто]

0 ответов

Похожие вопросы: