[RESOLVIDO]Complexidade espacial de algoritmo

A complexidade espacial dele é O(1) porque ele não aloca nenhuma memória adicional para reconhecer a expressão ab*c.

entanglement:

A complexidade espacial dele é O(1) porque ele não aloca nenhuma memória adicional para reconhecer a expressão ab*c.

Atenção: se seu algoritmo precisa achar uma subexpressão que bata com a expressão regular ab*c ele precisaria de fazer algo como backtracking, por exemplo - e nesse caso ele teria uma complexidade espacial diferente de O(1).

Obrigado entanglement

Eu realmente pensei que fosse O(1), já que eu aloco apenas a variável letra, e toda vez que leio, “salvo” nesta mesma variável.

Está certo isso?

Se seu algoritmo é esse mesmo (um match simples, não um “find” - e no caso de “find”, ele está errado ) então é realmente O(1).

De qualquer maneira, normalmente se faz a análise de algoritmos mais gerais que esse que você apresentou, que é apenas uma máquina de estados simples representada como um laço “while” e alguns ifs.

Sim, o algorítmo é este mesmo, um match simples.

Na verdade me foi pedido em um exercício de entrevista de emprego para criar um algorítmo que fizesse o match da expressão e que tivesse complexidade espacia O(1).

Ai quando entreguei, o avaliador ficou uma cara meio que “tá errado”, aí queria saber se estáva certo hehehe.

Vlw pela resposta!!

Acho que ele não gostou do “mara” - deve ter imaginado o Ítalo Rossi desmunhecando na frente dele ( http://imirante.globo.com/namira/noticias/2011/08/03/pagina281189.shtml )

Hehehhe, vai saber né.

iniciantejava89:

Sim, o algorítmo é este mesmo, um match simples.

Na verdade me foi pedido em um exercício de entrevista de emprego para criar um algorítmo que fizesse o match da expressão e que tivesse complexidade espacia O(1).

Ai quando entreguei, o avaliador ficou uma cara meio que “tá errado”, aí queria saber se estáva certo hehehe.

Vlw pela resposta!!

:shock:

Por curiosidade, era para java essa vaga ? :shock:

Eu não faço a mínima ideia do que seja essa tau de “Complexidade espacial”. :shock:

A propósito, você conferiu se o que você escreveu deu certo mesmo? Isto aqui está conferido.

class ABC {
    /* Reconhecer ab*c */
	
	public static boolean matchUsingStateMachine (String s) {
	    int state = 1;
		int n = 0;
	    while (state != 0 && n < s.length()) {
			char ch = s.charAt(n);
			switch (state) {
			case 1: 
				if (ch != 'a')
					return false;
				state = 2;
				break;
			case 2:
				if (ch == 'c' && n == s.length() - 1)
					return true;
				else if (ch == 'b')
					state = 2; // obviamente isto é dispensável, mas escrevo para ficar claro
				else
					return false;
				break;
			}
			n = n + 1;
		}
		return false;
	}
	public static boolean matchUsingWhile (String s) {
	    if (s.length() < 2)
			return false; // no mínimo a expressão é "ac"
		if (s.charAt(0) != 'a')
			return false;
		int n = 1;
		while (n < s.length() && s.charAt (n) == 'b')
			n++;
		if (n == s.length() - 1 && s.charAt (n) == 'c')
			return true;
		return false;
	}
		
	public static void main (String[] args) {
		System.out.println (matchUsingStateMachine ("abbbbbc"));
		System.out.println (matchUsingStateMachine ("abc"));
		System.out.println (matchUsingStateMachine ("ac"));
		System.out.println (matchUsingStateMachine ("acb"));
		System.out.println (matchUsingStateMachine (""));
		System.out.println (matchUsingStateMachine ("a"));
		System.out.println (matchUsingWhile ("abbbbbc"));
		System.out.println (matchUsingWhile ("abc"));
		System.out.println (matchUsingWhile ("ac"));
		System.out.println (matchUsingWhile ("acb"));
		System.out.println (matchUsingWhile (""));
		System.out.println (matchUsingWhile ("a"));
	}
}

A propósito, você conferiu se o que você escreveu deu certo mesmo? Isto aqui está conferido.

class ABC {  
    /* Reconhecer ab*c */  
      
    public static boolean matchUsingStateMachine (String s) {  
        int state = 1;  
        int n = 0;  
        while (state != 0 && n < s.length()) {  
            char ch = s.charAt(n);  
            switch (state) {  
            case 1:   
                if (ch != 'a')  
                    return false;  
                state = 2;  
                break;  
            case 2:  
                if (ch == 'c' && n == s.length() - 1)  
                    return true;  
                else if (ch == 'b')  
                    state = 2; // obviamente isto é dispensável, mas escrevo para ficar claro  
                else  
                    return false;  
                break;  
            }  
            n = n + 1;  
        }  
        return false;  
    }  
    public static boolean matchUsingWhile (String s) {  
        if (s.length() < 2)  
            return false; // no mínimo a expressão é "ac"  
        if (s.charAt(0) != 'a')  
            return false;  
        int n = 1;  
        while (n < s.length() && s.charAt (n) == 'b')  
            n++;  
        if (n == s.length() - 1 && s.charAt (n) == 'c')  
            return true;  
        return false;  
    }  
          
    public static void main (String[] args) {  
        System.out.println (matchUsingStateMachine ("abbbbbc"));  
        System.out.println (matchUsingStateMachine ("abc"));  
        System.out.println (matchUsingStateMachine ("ac"));  
        System.out.println (matchUsingStateMachine ("acb"));  
        System.out.println (matchUsingStateMachine (""));  
        System.out.println (matchUsingStateMachine ("a"));  
        System.out.println (matchUsingWhile ("abbbbbc"));  
        System.out.println (matchUsingWhile ("abc"));  
        System.out.println (matchUsingWhile ("ac"));  
        System.out.println (matchUsingWhile ("acb"));  
        System.out.println (matchUsingWhile (""));  
        System.out.println (matchUsingWhile ("a"));  
    }  
}

Na verdade eu não podia criar um método que recebesse a String inteira, pois ele falava que o programa aceitava um input por vez.
Então é como se fosse uma verificação em tempo de execução, a cada letra entrada.
Mas sim, eu conferi o algoritmo e ele funcionou, pelo menos com os testes que eu fiz hahaha.
Não precisei implementar a máquina de estados, pois era uma expressão simples.

Por curiosidade, era para java essa vaga ?

Eu não faço a mínima ideia do que seja essa tau de "Complexidade espacial".

Isso é análise de algoritmos, onde a análise pode ser feita temporalmente (vendo tempo de execução, ou vendo o número de iterações e/ou número de operações realizadas para resolver o problema)
ou espacial (vendo a memória utilizada para resolver o problema).