وقت التعقيد O () من ISPALINDROME ()

Question

لدي هذه الطريقة، iSpalindrome ()، وأنا أحاول العثور على تعقيد الوقت لذلك، وأيضا إعادة كتابة التعليمات البرمجية بشكل أكثر كفاءة.

boolean isPalindrome(String s) {
    boolean bP = true;
    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) != s.charAt(s.length()-i-1)) {
            bP = false;
        }
    }
    return bP;
}

الآن أعرف أن هذا الرمز يتحقق من أحرف السلسلة لمعرفة ما إذا كان هو نفسه ما قبله وإذا كان الأمر كذلك، فهذا لا يغير BP.

وأعتقد أنني أعرف أن العمليات هي S.Length ()، S.CHERAT (I) و S.CHERAT (S.Length () - I-!)).

جعل التعقيد الوقت O (N + 3)، أعتقد؟ هذا صحيح، إن لم يكن ما هو وكيف نفاد ذلك.

أيضا لجعل هذا أكثر كفاءة، هل سيكون من الجيد تخزين الشخصية في سلاسل مؤقتة؟

Answer 1

يبدو أن التعليمات البرمجية المعينة يجب أن يتحقق ما إذا كانت السلسلة palindrome عن طريق التحقق من الحرف "N" هي نفس الحرف "طول". كما ذكرنا بالفعل، يمكنك زيادة الكفاءة من قبل

• فقط التحقق من النصف الأول
• الخروج (عودة خطأ) بمجرد أن تجد غير متطابقة

لتلك الاقتراحات، سأضيف

• لا تقم بإعادة حساب S.Length () بشكل متكرر في كل مرة من خلال الحلقة لأنه لا يتغير.

بالنظر إلى كل ما يلي:

boolean isP(String s) {
  int l = s.length();
  int l2 = l/2;
  int j = l - 1;
  for(int i=0; i<l2; i++) {
    if(s.charAt(i) != s.charAt(j)) {
        return false;
    }
    j--;
  }
  return true;
}

Answer 2

انها مجرد O (ن).

قائلا o (n + 3) ليس عوامل ثابتة ذات معنى حقا.

يمكنك أن تجعل الأمر أسرع عن طريق الخروج عندما يجد عدم تطابق:

bP = false;
break;

(ليس هذا يغير حقيقة أنه س (ن)، لكنه سوف يسرعه في معظم الحالات.)

هذا ليس صحيحا:

يتحقق هذا الرمز أحرف السلسلة لمعرفة ما إذا كان هو نفسه واحد قبل ذلك

يتحقق من أن الشخصيات في البداية تطابق تلك الموجودة في النهاية، لذلك وبعبارة أخرى ساذج palindrome. فاحص.

تسريع آخر سوف حلقة حتى s.length()/2 - وإلا فإنك تقوم بجميع المقارنات مرتين للحصول على سلسلة بالخيل.

Answer 3

هذا هو الأكثر احتمالا التنفيذ الأكثر كفاءة في Java:

    public static boolean isP(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < (chars.length / 2); i++) {
            if (chars[i] != chars[(chars.length - i - 1)])
                return false;
        }
        return true;
    }

فوائد:

• عوائد من النظرة الأولى من الفرق.
• يستخدم char المباشر [] الوصول إلى تجنب الشيكات الكبرى في charat
• فقط تكرار نصف السلسلة، على عكس السلسلة الكاملة.

هو، مثل كل الحلول المقترحة الأخرى، لا تزال س (ن).

أنا فقط تقاس الوقت الحلول المقدمة للحصول على سلسلة كبيرة حقا (مرات في nanoseconds):

 Aran:           32244042
 Andreas:        60787894
 Paul Tomblin:   18387532

أولا، تم القياسات المذكورة أعلاه مع عميل VM.. وبعد وهكذا الحساب i < (chars.length / 2) لم ينطوي كمستمر. باستخدام المعلمة -Server VM أعطى نتيجة أفضل بكثير:

 Aran:           18756295
 Andreas:        15048560
 Paul Tomblin:   17187100

لقيادتها شديدة:

---

كلمة تحذير أولا: لا تستخدم هذا الرمز في أي برنامج تنوي استخدامه / السفينة.

---

أنه يحتوي على أخطاء خفية ولا يطيع جافا api. وليس له خطأ في التعامل مع الأخطاء، كما هو مذكور في التعليقات. إنه يخدم بحتة لإظهار تحسينات الأداء النظرية التي يمكن الحصول عليها بواسطة الحيل القذرة.

هناك بعض النفقات العامة عند نسخ الصفيف من السلسلة، لأن فئة السلسلة تحدث داخليا نسخة دفاعية.

إذا حصلنا على Char Char الأصلي [] من السلسلة مباشرة، فيمكننا الضغط على القليل من الأداء، بتكلفة استخدام عمليات الانعكاس والعمليات غير المدقة على السلسلة. هذا يحصل لنا أداء 20٪ آخر.

public static boolean isPReflect(String s) {
    char[] chars = null;
    try {
        final Field f = s.getClass().getDeclaredField("value");
        f.setAccessible(true);
        chars = (char[]) f.get(s);
    }
    catch (IllegalAccessException e) {
    }
    catch (NoSuchFieldException e) {
    }

    final int lenToMiddle = chars.length / 2;
    for (int i = 0; i < lenToMiddle; i++) {
        if (chars[i] != chars[(chars.length - i - 1)]) 
            return false;
    }
    return true;
}

مرات:

 Aran:           18756295
 Andreas1:       15048560
 Andreas2:       12094554
 Paul Tomblin:   17187100

Answer 4

إنه متصل). أنت تقوم بإجراء مقارنات N، حيث n = s.length (). كل مقارنة تأخذ O (1) الوقت، لأنها مقارنة حرف واحد.

+3 لا يهم، كما يهتم التدوين مقارب فقط بأعلى مدة الطلب.

Answer 5

إليك حل آخر مع اثنين من المؤشرات المعاكسة:

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
        ++i;
        --j;
    }
    return i >= j;
}

التعقيد مرة أخرى في(ن).

الذهاب أكثر قليلا إلى التفاصيل: دعنا نقول كل عملية تكاليف 1 وحدة. مقارنات، المهام، العمليات الحسابية، وظيفة تستدعي كل وحدة تكلفة 1. لذلك دعوة isPalindrome التكاليف في أسوأ الحالات (s هل يأخذ Palindrome) على سبيل المثال:

  4 + n/2 · (3 + 4) + 1
= 5 + n/2 · 7
= 5 + 7/2 · n

وبما أن العامل المستمر (هنا 5 + 7/2) تم حذفه، ونحن في نهاية المطاف مع 5 + 7/2 · ن ∈ في(ن).

Answer 6

أولا، لا يمكن أن يكون هناك حل موضوع واحد لهذه المشكلة حيث تعقيد "الأسوأ" أفضل من O(N) للحصول على سلاسل الإدخال التعسفي. ببساطة، يجب أن ننظر أي خوارزمية في كل شخصية في السلسلة في أسوأ الحالات. من الناحية النظرية يمكنك تحسين O(N) باستخدام موازي الأجهزة؛ أي لديهم عدد قابلة للتطوير غير مسمى من المعالجات التي تعمل على أجزاء مختلفة من السلسلة. في الممارسة العملية، سيكون من الصعب تحقيق أي تسريع على الإطلاق. ستكون تكلفة إرسال سلسلة الإدخال (أو الأجزاء ذات الصلة) لكل معالج "س (ن)"، إلا إذا كان هناك بعض الحل الذي لا أعرفه.

ثانيا، كما ترون O(N) السلوك ليس الجواب الأخير. تحتاج أيضا إلى النظر في ثابت مضاعف مثل N -> اللانهاية، والشروط الأقل لقيم n.

ثالثا، @ DFA يقول إنه ليس عملك على التحسين الصغير. إنه على المسار الصحيح، لكنني لا أعتقد أنه من القطع الواضح تماما. IMO، إنه مضيعة للوقت الصغرى الأمثل ما لم 1) طلبك حقا يحتاج إلى تشغيل أسرع وقت ممكن، و 2) يوضح تنموبي التطبيق أن هذا الحساب معين حقا هي رقبة زجاجة كبيرة.

أخيرا، قد تجعل برنامج التحسين الصغير الذي يجعل برنامج أسرع لمجموعة منصة / جيت منصة جيت واحدة معينة، مما يجعله أبطأ لآخر واحد. الكود المعقدة الصغير الأمثل هو أصعب لجهاز مترجم JIT لتوليد رمز فعال ل. وإذا كنت تستخدم التفكير للوصول إلى Interals of (Say) فئة السلسلة، فقد يفشل التعليمات البرمجية الخاصة بك في بعض الأنظمة الأساسية. (لا يوجد شيء في مواصفات مكتبة الفئة Java تقول أن سلسلة لديها حقل خاص يسمى "القيمة" char[]!!!)

Answer 7

أولا وقبل كل شيء، ما هي الطريقة التي من المفترض أن تفعلها؟

تخميني: تحديد ما إذا كانت السلسلة palindrome..

من الواضح تماما، لن تكون قادرا على إلقاء الضوء عليها تحت O (N):

O(N+3) == O(N)

السؤال الآخر هو، هل هو الحل الأكثر كفاءة؟ ربما لا.

مجال للتحسين:

1. قطعها في النصف. يمكنك التحقق من جميع الشخصيات مرتين (مثل Michiel Buddingh المقترحة).

2. الحصول على صفيف الشخصية مسبقا. أن يغضب لك بعض الشيكات الفهرس التي تحدث في الداخل chatAt().

جميع العمليات الأخرى، charAt() و length(), ، هل (1) مع تنفيذ السلسلة القياسية.

Answer 8

التحسين الأول: يمكنك كسر بمجرد العثور على عدم التسجيل، أليس كذلك؟

Answer 9

على افتراض أن العمليات في حلقةك يمكن تنفيذها في وقت ثابت، فإن التعقيد س (ن). نظرا لأن "Big-O" تدابير تدوين النمو، وليس السرعة النقية، يمكن تجاهل العوامل المستمرة. هذا يتركنا باستنتاج مفاده أن O (N + 3) يساوي o (n).

Answer 10

كبير O. التعقيد دائما بدون رطفة (منذ N-> OO، فهي غير مهمة). لذلك تعقيد وقتك ببساطة O(n).

أيضا لجعل هذا أكثر كفاءة، هل سيكون من الجيد تخزين الشخصية في سلاسل مؤقتة؟

هذه ليست عملك. سوف يعالج مترجم JIT هذا التحسين الصغير لك.

Answer 11

يمكنك قص تعقيد الوظيفة في النصف من خلال التوقف عند (I == (S.Length () / 2) +1). إنه غير مناسب بشروط كبيرة، لكنه لا يزال مكسبا لائق جدا.

Answer 12

أو يمكنك فقط القيام به

def isPalindrome?(x)
 return x == x.reverse
end

هذا لا يزال O (ن) تعقيد الوقت.