sou novo aqui e queria esclarecer uma dúvida. Tenho o seguinte código (verica o match da expressão ab*c) e gostaria de saber qual a complexidade espacial dele:
boolean mara = true;
Scanner in = new Scanner(System.in);
String letra = in.next();
if (!letra.equals("a")) {
System.out.println("ERRO!");
mara = false;
} else {
while (!(letra = in.next()).equals("c")) {
if (!letra.equals("b")) {
System.out.println("ERRO!");
mara = false;
break;
}
}
}
if (mara) {
System.out.println("Mara");
}
[quote=entanglement]A complexidade espacial dele é O(1) porque ele não aloca nenhuma memória adicional para reconhecer a expressão ab*c.
[/quote]
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).
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.
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.
[quote=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!![/quote]
: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:
[quote]A propósito, você conferiu se o que você escreveu deu certo mesmo? Isto aqui está conferido.
[code]
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"));
}
}[/code]
[/quote]
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.
[quote]
Por curiosidade, era para java essa vaga ?
Eu não faço a mínima ideia do que seja essa tau de “Complexidade espacial”. [/quote]
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).
) então é realmente O(1).