Понимание Big-O на конкретном примере - PullRequest
Новая
       79

Понимание Big-O на конкретном примере

0 голосов
/ 15 мая 2018

Я работаю над довольно простым вопросом, чтобы убедиться, что я понимаю эти понятия.

Вопрос в том, что существует массив A из n элементов: RED, WHITE или BLUE. Переставьте массив таким образом, чтобы все элементы WHITE были перед всеми элементами BLUE, а все элементы BLUE - перед всеми элементами RED. Построить алгоритм в O (n) времени и O (1) пространстве.

Насколько я понимаю, псевдокод для решения будет: 

numW = numB = 0
for i = 0 to n:
    if ARRAY[i] == WHITE:
        numW++
    else if ARRAY[i] == BLUE:
        numB++

for i = 0 to n:
    if numW > 0:
        ARRAY[i] = WHITE
        numW--
    else if numB > 0:
        ARRAY[i] = BLUE
        numB--
    else:
        ARRAY[i] = RED

Я считаю, что это O (n), потому что он проходит через цикл дважды, а O (2n) находится в O (n). Я полагаю, что пространство равно O (1), потому что оно не зависит от общего количества элементов, то есть всегда будет счет для каждого

Правильно ли мое понимание?

Ответы [ 3 ]

0 голосов
/ 15 мая 2018

Да, ваше решение выполняется за время O (n) в пространстве O (1).

Ниже мое решение, которое также работает в O (n) времени и O (1) пространстве, но также работает, когда у нас есть ссылки на объекты, как @kenneth предложил в комментариях. 

import java.util.Arrays;
import java.util.Random;
import static java.lang.System.out;

class Color{
    char c;
    Color(char c){
        this.c = c;
    }
}

public class Solution {

    private static void rearrangeColors(Color[] collection){
        int ptr = 0;   

        // move all whites to the left

        for(int i=0;i<collection.length;++i){
            if(collection[i].c == 'W'){
                swap(collection,ptr,i);
                ptr++;
            }
        }

        // move all blacks to the left after white       

        for(int i=ptr;i<collection.length;++i){
            if(collection[i].c == 'B'){
                swap(collection,ptr,i);
                ptr++;
            }
        }
    }

    private static void swap(Color[] collection,int ptr1,int ptr2){
        Color temp = collection[ptr1];
        collection[ptr1] = collection[ptr2];
        collection[ptr2] = temp;
    }

    private static void printColors(Color[] collection){
        for(int i=0;i<collection.length;++i){
            out.print(collection[i].c + ( i != collection.length - 1 ? "," : ""));
        }
        out.println();
    }

    public static void main(String[] args) {
        // generate a random collection of 'Color' objects
        Random r = new Random();
        int array_length = r.nextInt(20) + 1;// to add 1 if in case 0 gets generated 
        Color[] collection = new Color[array_length];
        char[] colors_domain = {'B','W','R'};

        for(int i=0;i<collection.length;++i){
            collection[i] = new Color(colors_domain[r.nextInt(3)]);
        }

        // print initial state
        printColors(collection);
        // rearrange them according to the criteria
        rearrangeColors(collection);
        // print final state
        printColors(collection);        
    }

}
0 голосов
/ 16 мая 2018

Я не скажу, что это на 100% правильно, но быстрый тестовый пример здесь сработал. Во всяком случае, это показывает идею возможности сделать это за один проход. Это быстрее? Возможно нет. Я считаю, что ответ ОП по-прежнему лучший в этом случае. 

#include <stdio.h>

char temp;
#define SWAP(a,b) { temp = a; a = b; b = temp;}

int main()
{
    int n = 10;
    char arr[] = "RWBRWBRWBR";
    printf("%s\n", arr);

    int white = 0;

    for(int i=0; i<n; i++)
    {
        if(arr[i] == 'B')
        { 
            SWAP(arr[i], arr[n-1]);
            i--; n--;
        }
        else if(arr[i] == 'R')
        {
            SWAP(arr[i], arr[white]);
            white++;
        }
    }

    printf("%s\n", arr);
}
0 голосов
/ 15 мая 2018

Если это линейное время, и ваш алгоритм выглядит так, то это O (n), как вы подозреваете.Вот отличная сводка: Big-O для восьмилетних?

...