Comment Réduire le Temps de la Complexité

Hier, j'ai assisté à une entrevue. Il m'a donné quelques questions de programmation à résoudre. Lorsque j'ai résolu eux, l'enquêteur a dit qu'il peut être fait dans le meilleur Moment de la complexité. J'étais tellement déprimé que je ne peux pas faire le programme dans le meilleur moment de la complexité. Enfin, je ne suis pas capable de passer à travers le processus d'entrevue. Mais ce que je veux savoir, c'est comment pouvons-nous faire au meilleur moment pour n'importe quel problème? Quel devrait être mon approche pour atteindre cet état? Je sais que la réponse parfaite est pratique. Mais encore, je veux savoir comment et de quelles façons de faire un programme tel qu'il fonctionne dans moins de temps et d'utiliser le meilleur de la mémoire. Ce que les livres que je dois lire? Quels sont les problèmes que je pratique?

P. S: je sais que ce n'est pas une question technique. Mais s'il vous plaît laissez-moi savoir comment je peux faire cela.

  • u pourrait donner un exemple? peut-être la raison pour laquelle il n'a pas de location d'une autre? difficile de le dire.
  • Vous êtes conscient que la meilleure approche à un problème de dépend du problème, droit? Il n'y a pas de biscuit-coupeur de solutions. Non, même pas jQuery.
  • Il y a deux tableaux de dire B[], Un[]. Ces deux sont de taille n. Maintenant, j'ai besoin de calculer B[0 à n-1] tel que B[0] = A[1] * A[2] * A[3] ... A[n-1] B[1] = A[0] * A[2] * A[3] ... A[n-1] sna ainsi de suite. C'est pour tous les B-tableau de 0 à n de l'index j'ai besoin de faire la multiplication d'Un tableau[] à l'exception de l'élément qui a l'indice de B pour laquelle nous sommes le calcul. J'ai fait un en O(n^2) il m'a dit, il peut être fait en O(n). Ne pouvait pas comprendre comment le faire? Simillarly peu plus de questions.
  • Vous devez apprendre à mieux faire face à ce genre de question d'entrevue. Il est déraisonnable de s'attendre à ce que quelqu'un connaît le "meilleur" de l'algorithme pour chaque problème, donc raisonnable de l'intervieweur n'a pas de telles attentes et vous ne devriez pas non plus. Je est raisonnable d'attendre des candidats de connaître les meilleurs algorithmes (notez le pluriel) pour une (petite) série de problèmes de base (tri, la recherche, le domaine spécifique des choses (nombre de croquant dans mon cas), ...) et d'être en mesure d'appliquer leurs connaissances des algorithmes à des problèmes nouveaux tels que ceux qui sont jetés dans une interview.
  • Vous pouvez affecter la valeur de A[0]*A[1]*..*A[n-1] dans une variable appelée mulA, alors pour chaque i de 0 à n - 1, vous pouvez affecter à B[i] est égal à mulA / A[i]. Calcul de mulA peut être fait dans O(n) et plus tard partie nécessite un autre O(n) complexité. Et O(n) + O(n) est en fait O(n).
  • 100% d'accord avec vous. Il y a quelques problèmes qui pourraient avoir une seule solution optimale et de toutes les industries sont ce qui nous attend pour le savoir. Filaire, mais c'est la vérité.

InformationsquelleAutor Amarnath | 2012-07-31
  1. 6

    L'un des meilleurs livres sur les algorithmes, structures de données, le temps et l'espace de la complexité est Introduction aux Algorithmes. Je peux également vous recommander de lire les livres suivants pour une bonne préparation pour une entrevue:

    1. Les fissures de Codage Interview: 150 Questions de Programmation et de Solutions
    2. La programmation des Entretiens Exposés: les Secrets de l'Atterrissage de Votre Prochain Emploi
    3. La Programmation Des Perles
    InformationsquelleAutor Ivan Kruglov
  2. 3

    Résoudre ce genre de problème implique la pratique, plus de "voir le truc". Pour cet exemple précis, vous remarquerez que les B[i] = P/A[i], où P est le produit de tous les A[i] éléments multipliés. Dans ce cas, en O(n) vient de calculer, en premier lieu P une fois (n-1 multiplications), suivie par le calcul de chaque B[i] (un autre n divisions).

    Parfois, la meilleure façon de "voir ce truc" est à la recherche de motifs répétés dans l'algorithme que vous utilisez. Pour votre exemple, remarque que dans votre description vous fait de la saisie de la chaîne de "A[2] * A[3] ... A[n-1]" deux fois, donc c'est le genre de lieu de penser "je peux faire cette chose une seule fois dans l'algorithme".

    • Merci. Je pense que c'est ce qu'il me disait dans l'interview qu'il y a un aspect du motif .. regarde .. regarde ..:(
    InformationsquelleAutor Penguino
  3. 1

    Lire un grand nombre d'algorithmes et de la pratique.

    La résolution de problèmes en ligne, des juges est également utile pour augmenter l'efficacité et la précision de la compétence de résolution des problèmes.

    Liste de certains juges sont donnés ci-dessous:

    InformationsquelleAutor Rupak