[ Beispielalgorithmus 1 ]: Ich habe ein Array von structs( PaymentReceipt[] paymentReceiptList;) und stelle mir vor, dass es ungefähr 1000 geschobene Elemente gibt und die Größe des Arrays weiter zunimmt. Jedes Element hat einen time_start- und einen time_end-Wert. Innerhalb der Funktion meines Vertrags muss ich alle diese Mitglieder iterieren, um zu prüfen, ob sich zwei Intervalle in einem bestimmten Satz von Intervallen überschneiden , was O(n) Zeit ist.
[ Beispielalgorithmus 2 ]: Ich verwende eine Algorithmusfunktion, um die n-te Fibonacci-Zahl zu berechnen , um den 1000. Wert zu finden. Dies ist eine rekursive Funktion zur Berechnung der n-ten Fibonacci-Zahl und hat eine Zeit von O(log(n)).
Für Algorithmus_1 mit einem kleinen Satz und für Algorithmus_2 , wenn der n-te Wert klein ist, sollte es kein Problem geben. Aber große Größe des Arrays auf Algorithm_1 und großer Wert für n auf Algorithm_2 , kann ich mit ineffizientem Gasproblem konfrontiert werden. Ich war mir nicht sicher, ob diese beiden Algorithmen eine hohe Menge an Gas verbrauchen werden oder nicht, basierend auf den gegebenen n. Ich möchte den höchsten Wert ermitteln, den nich für beide Algorithmen verwenden kann, basierend auf der gegebenen Gasmenge.
[F] Ist es ratsam, O(n)- und O(log(n))-Zeitalgorithmen innerhalb einer Vertragsfunktion auszuführen, wenn ja, gibt es eine Möglichkeit, das erforderliche Gas als eine Art Funktion basierend auf den gegebenen nfür zu schätzen jeder Algorithmus?
=> Bezieht sich auf vorherige Frage; Ändert sich das verwendete Gas für jeden Algorithmus im gleichen Verhältnis mit der Zeit O()?
Zum Beispiel: Für Algorithmus_1 : Können wir sagen, dass das verwendete Gas das gleiche Verhältnis zur O(n)-Zeit hat.
O((n=10)) usedGas=10
O((n=100)) usedGas=100
O((n=1000)) usedGas=1000
Für Algorithmus_2 : oder können wir sagen, dass das verwendete Gas das gleiche Verhältnis zur O(log(n))-Zeit hat.
O(log(n=10)) usedGas=10
O(log(n=100)) usedGas=20
O(log(n=1000)) usedGas=30
Vielen Dank für Ihre wertvolle Zeit und Hilfe.
Algo 1: Sie sollten es so implementieren, dass beim Hinzufügen eines Intervalls sofort überprüft wird, ob es sich mit den vorhandenen überschneidet. Anschließend speichern Sie das Ergebnis dieser Prüfung im Speicher. Nicht einfach, denn das würde bedeuten, 1 oder 2 geordnete Listen zu führen. Dies könnte O(log n) werden und sollte daher ohne Aufblasen von Gas möglich sein.
Algo 2: Die von Ihnen verlinkte Berechnung sieht für mich wegen der for (int i=2;i<n;i++)Schleife O(n) aus. Andererseits sieht es so aus, als hätten die Leute O(1)-Berechnungen für Fibonacci: https://stackoverflow.com/questions/6037472/can-a-fibonacci-function-be-written-to-execute-in-o1- Zeit
Sie sollten keine O(n)-Berechnungen durchführen oder, falls doch, diese auf mehrere Transaktionen verteilen. Der Weg, dies zu tun, besteht darin, auf verbleibendes Gas zu prüfen und den Zwischenzustand zu speichern, wenn er niedrig wird.
O (log n) ist in Ordnung.
Gasberechnungen hängen auch davon ab, ob Sie sich if then elseinnerhalb der Schleife befinden. Diese Verzweigungsanweisungen beeinflussen die Gaskosten jeder Ausführung der Schleife. Ich sehe also keine schöne Gasberechnung, bevor Sie es tatsächlich versuchen ...
Alper
if then else. Soll ich das verbleibende Gas während der Laufzeit des Codes überprüfen? Was meinst du mit Zwischenzustand? @Xavier Leprêtre B9lab. PS: Ich habe den Link für Algoritm_2 mit O (log (n)) aktualisiertXavier Leprêtre B9lab