هل يمكننا حساب هذا في أقل من O (n*n) ... (nlogn أو n)

Question

هذا سؤال طرحه لي من قبل MNC مشهورة جدًا. السؤال كما يلي ...

أدخل صفيف 2D n*n من 0 و 1. إذا كان A (i ، j) = 1 ، فإن جميع القيم المقابلة لصف ITH والعمود JTH ستكون 1. إذا كان هناك 1 بالفعل ، فسيظل ذلك 1.

على سبيل المثال ، إذا كان لدينا الصفيف

  1 0 0 0 0 
  0 1 1 0 0 
  0 0 0 0 0 
  1 0 0 1 0
  0 0 0 0 0

يجب أن نحصل على الإخراج

 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 0
 1 1 1 1 1
 1 1 1 1 0

مصفوفة الإدخال مكتظة بالسكان.

هل هذا ممكن في أقل من O (n^2)؟

لم يتم توفير مساحة إضافية كانت حالة أخرى. أود أن أعرف ما إذا كانت هناك طريقة لتحقيق التعقيد باستخدام مساحة <= o (n).

ملاحظة: لست بحاجة إلى إجابات تعطيني تعقيدًا من O (n*n). هذه ليست مشكلة في الواجب المنزلي. لقد جربت الكثير ولم أستطع الحصول على حل مناسب واعتقدت أنه يمكنني الحصول على بعض الأفكار هنا.

كانت فكرتي التقريبية هي القضاء ديناميكيًا على عدد العناصر التي تم اجتيازها إلى حوالي 2N أو نحو ذلك. لكنني لم أستطع الحصول على فكرة مناسبة.

Answer 1

مرحبا يا رفاق ،

بفضل التعليق من MB14 ، أعتقد أنه يمكنني حلها في أقل من O (Nن) الوقت ... الأسوأ سيستغرق o (nن)...

في الواقع ، لدينا صفيف معين يفترض

  1 0 0 0 1
  0 1 0 0 0 
  0 1 1 0 0 
  1 1 1 0 1
  0 0 0 0 0 

دعنا نحصل على صفيفان من الحجم n (سيكون هذا هو أسوأ حالة) ... واحدة مكرسة لفهرسة صفوف وأعمدة أخرى ... ضع تلك مع [i] [1] = 0 في صفيف واحد ثم a [1 ] [J] = 0 في آخر ..

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

يمنح عدد القيم في صفيف الصف رقم 0 في صفيف النتائج والنقطة A [قيم صفي الصفوف] [قيمة صفيف الأعمدة] تمنحك تلك النقاط ....

يمكننا حلها في أدناه o (نn) والأسوأ هو o (نن) ... كما يمكننا أن نرى ، تتناقص المصفوفات (من الحجم ن) ....

لقد فعلت هذا لبضع صفائف وحصلت على نتيجة لهم جميعًا ... :)

الرجاء تصحيحني إذا كنت مخطئا في أي مكان ...

Thanx لجميع تعليقاتك يا رفاق ... أنت كلها مفيدة للغاية وقد تعلمت بعض الأشياء على طول الطريق ... :)

Answer 2

في أسوأ الحالات ، قد تحتاج إلى تبديل بت من 0 إلى 1 لإنشاء الإخراج. يبدو أنك عالق جيدًا مع O (n*n).

Answer 3

أتصور أنه يمكنك تحسينه للحصول على أفضل حالة ، لكنني أميل إلى القول إن أسوأ حالتك لا تزال O (n*n): ستكون أسوأ حالتك عبارة عن مجموعة من جميع 0s ، وسيتعين عليك فحصها كل عنصر واحد.

سيتضمن التحسين تخطي صف أو عمود بمجرد العثور على "1" (يمكنني تقديم التفاصيل ، لكنك قلت أنك لا تهتم بـ o (n*n) الصف/العمود بأكمله فارغ ، أو ما لم يكن لديك طريقة على غرار SIMD للتحقق من حقول متعددة في وقت واحد (على سبيل المثال ، إذا تم محاذاة كل صف بمقدار 4 ، ويمكنك قراءة 32 بت البيانات ، أو إذا كانت بياناتك في شكل من أشكالها بضع ماسك) ، سيكون عليك دائمًا التعامل مع مشكلة مجموعة All-Zero.

Answer 4

من الواضح ، ولا يجب أن تكون مصفوفة الإخراج ولا نسختها المنقولة متفقة (خذ مصفوفة مع نصف الصف الأول تم تعيينه على 1 وأي شيء آخر إلى 0 . (أفترض أن المدخلات هي قائمة بالعناصر أو أي شيء مكافئ ، لأنه وإلا فإنك لا تستطيع الاستفادة من المصفوفة المتفجرة.)

حل بسيط للمساحة والوقت O (M+N) (M هو عدد تلك الموجودة في مصفوفة الإدخال): خذ صفائف من الطول n مملوءة بأخرى ، وتكرار من خلال جميعها في المدخلات ، ولكل قطرة x التنسيق من المصفوفة الأولى و y من الثانية. الناتج هو المصفوفتين ، اللذين يحددان بوضوح مصفوفة النتيجة: إحداثيات (x ، y) هو 0 iff إحداثيات x للمصفوفة الأولى والإحداثيات y للثانية هي 0.

تحديث: اعتمادًا على اللغة ، يمكنك استخدام بعض الخداع لإرجاع صفيف ثنائي الأبعاد عادي عن طريق الرجوع إلى نفس الصف عدة مرات. على سبيل المثال في PHP:

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

بالطبع هذه مجموعة طبيعية فقط طالما أنك لا تحاول كتابتها.

Answer 5

نظرًا لأن كل إدخال من المصفوفة يجب فحصه ، فإن أسوأ حالتك ستكون دائمًا.

مع سعة تخزين إضافية 2*n ، يمكنك إجراء العملية في O (n*n). ما عليك سوى إنشاء قناع لكل صف وآخر لكل عمود - قم بفحص الصفيف وقم بتحديث الأقنعة أثناء ذهابك. ثم مسح مرة أخرى لملء مصفوفة النتيجة بناءً على الأقنعة.

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

Answer 6

قد تكون مصفوفة الإدخال متفقة ، ولكن ما لم تتمكن من الحصول عليها بتنسيق متناثر (أي قائمة من (i,j) الأزواج التي يتم تعيينها في البداية) ، مجرد قراءة مدخلاتك سوف تستهلك ω (n^2) الوقت. حتى مع الإدخال المتفرق ، من السهل أن ينتهي الأمر بإخراج O (n^2) للكتابة. كغش ، إذا سُمح لك بإخراج قائمة من الصفوف المحددة والعمود ، فيمكنك الوصول إلى الوقت الخطي. لا يوجد سحر يجب أن يكون عليه عندما يتعين على الخوارزمية بالفعل أن تنتج نتيجة أكثر جوهرية من "نعم" أو "لا".

يشير تعليق McDowella على إجابة أخرى إلى تنسيق إدخال بديل آخر: ترميز طول الجري. بالنسبة للمدخلات المتفرقة ، لا يتطلب ذلك بوضوح أكثر من وقت O (n) لقراءته (ضع في اعتبارك عدد التحولات التي تتراوح بين 0 و 1). ومع ذلك ، من هناك ينهار. النظر في مصفوفة الإدخال منظمة على النحو التالي:

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

وهذا هو ، بالتناوب 0 و 1 في الصف الأول ، 0 في أي مكان آخر. من الواضح أن هناك n/2 تلك في المجموع. ومع ذلك ، يجب أن يكرر إخراج RLE هذا النمط في كل صف ، مما يؤدي إلى إخراج O (n^2).

Answer 7

قول انت:

يجب أن نحصل على الإخراج كما ...

لذلك تحتاج إلى إخراج المصفوفة بأكملها ، والتي لديها عناصر n^2. هذا هو (ن*ن).

المشكلة نفسها ليست O (n*n): لا يتعين عليك حساب المصفوفة بأكملها وتخزينها: تحتاج فقط إلى متجهين ، L و C ، كل من الحجم n:

L [X] هو 1 إذا كان السطر X هو خط من تلك ، 0 خلاف ذلك ؛

C [X] هو 1 إذا كان السطر X هو خط من تلك ، 0 خلاف ذلك ؛

يمكنك بناء هذه المتجهات في O (n) ، لأن المصفوفة الأولية متناثرة ؛ لن تكون بيانات الإدخال الخاصة بك مصفوفة ، ولكن قائمة تحتوي على الإحداثيات (السطر ، العمود) لكل عنصر غير صفري. أثناء قراءة هذه القائمة ، قمت بتعيين L [line] = 1 و C [العمود] = 1 ، ويتم حل المشكلة: m [l ، c] == 1 إذا l [l] == 1 أو c [c] = = 1

Answer 8

من الواضح أن هناك ما يصل O(N^2) العمل للقيام به. في المصفوفة

1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

يجب ضبط جميع البتات على 1 ، و N*(N-1) لم يتم ضبطها على واحد (20 ، في هذه الحالة 5x5).

على العكس من ذلك ، يمكنك الخروج بخوارزمية تفعل ذلك دائمًا O(N^2) الوقت: SUM على طول الصف العلوي واترك العمود ، وإذا كان الصف أو العمود يحصل على إجابة غير صفرية ، املأ الصف أو العمود بأكمله ؛ ثم حل المشكلة الأصغر (N-1) X (N-1).

لذلك هناك حالات يجب أن تأخذ على الأقل N^2 وأي حالة يمكن حلها في N^2 بدون مساحة إضافية.

Answer 9

إذا كانت المصفوفة الخاصة بك متفرقًا ، فإن التعقيد يعتمد كثيرًا على ترميز المدخلات وعلى وجه الخصوص لم يتم قياسه جيدًا في NN² أو شيء من هذا القبيل ولكن من حيث n تعقيد الإدخال الخاص بك m^في و تعقيد الإخراج الخاص بك م^خارج. كنت أتوقع شيئًا مثل O (n + m^في + م^خارج) ولكن اعتمادا على الترميز والحيل التي يمكنك اللعب بها.

Answer 10

هذا يعتمد بالكامل على بنية بيانات الإدخال الخاصة بك. إذا قمت بتمرير المصفوفة (1s و 0s) كصفيف ثنائي الأبعاد ، فأنت بحاجة إلى اجتيازها وهذا هو (n^2). ولكن نظرًا لأن بياناتك قليلة ، إذا قمت فقط بتمرير 1 كمدخلات ، فيمكنك القيام بذلك بحيث يكون Ouptut O (M) ، حيث لا يكون M هو عدد الخلايا ولكن عدد الخلايا 1. سيكون شيئًا مشابهًا لهذا (الرمز الكاذب أدناه):

list f(list l) {
   list rows_1;
   list cols_1;

    for each elem in l {
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    list result;
    for each row in rows_1 {
        for each col in cols_1 {
             if (row == 1 || col == 1) {
                 add(result, new_elem(row, col));
             }
        }
    } 
   return result;
}

Answer 11

لا تملأ مركز المصفوفة عند التحقق من القيم. أثناء مرور العناصر ، عندما يكون لديك 1 تعيين العنصر المقابل في الصف الأول والعمود الأول. ثم العودة وملء وعبر.

تحرير: في الواقع ، هذا هو نفس آندي.

Answer 12

ذلك يعتمد على بنية البيانات الخاصة بك.

لا يوجد سوى حالتان محتملتان للصفوف:

• تم ملء صف I expied بـ 1 إذا كان هناك عنصر (i ، _) في الإدخال
• جميع الصفوف الأخرى هي نفسها: أي العنصر j-th هو 1 iff هناك عنصر (_ ، j) في الإدخال.

وبالتالي يمكن تمثيل النتيجة بشكل مضغوط كمجموعة من الإشارات إلى الصفوف. نظرًا لأننا بحاجة فقط إلى صفين ، فإن النتيجة لن تستهلك سوى ذاكرة O (n). على سبيل المثال ، يمكن تنفيذ ذلك في بيثون على النحو التالي:

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

ستكون مكالمة عينة

 f([(1,1),(2,2),(4,3)],5)

ونتيجة ل

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

النقطة المهمة هي أن المصفوفات لم يتم نسخها هنا ، أي [الصف] = A مجرد مهمة مرجعية. وبالتالي فإن التعقيد هو o (n+m) ، حيث m هو طول الإدخال.

Answer 13

#include<stdio.h>

تضمن

int main () {int arr [5] [5] = {{1،0،0،0،0} ، {0،1،1،0،0} ، {0،0،0،0،0} ، {1،0،0،1،0} ، {0،0،0،0،0}} ؛ int var1 = 0 ، var2 = 0 ، i ، j ؛

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

يستفيد هذا البرنامج من 2 4 متغيرات مؤقتة فقط (Var1 و Var2 و I و J) وبالتالي يتم تشغيله في مساحة ثابتة مع تعقيد الوقت O (n^2) .. أعتقد أنه من غير الممكن على الإطلاق حل هذه المشكلة في << س (ن^2).